Судоку

[Esp]

Коллеги, нет ли у вас ссылки на доказательство того, что это NP complete проблема ? По крайней мере в википедии написано что это именно так, но их ссылка на док-во, к сожалению, битая.

[незваный гость]

Здесь ссылки небитые

[geomath]

Обычно судоку в метро решают женщины. А сегодня я видел мужчину. Но судоку у него другой формы. Большой квадрат, как обычно, 9х9. В центре - симметричный крест из 9 ячеек, в каждом углу которого - по маленькому квадрату 3х3. Оставшиеся четыре фигуры, каждая в форме С, заполняют четыре угла большого квадрата. В начальной расстановке я насчитал 19 цифр. Мужчина думал-думал, думал-думал и поставил одну цифру. Потом подумал еще немного, бросил и взялся за другую головоломку. Не по зубам орешек оказался.

[geomath]

Посмотрите, какая идея а-ля судоку-какуро пришла тут мне в голову.

[photon]

Сам эту книгу не видел, но наткнулся в анонсах по выходу книг:

Цитата:

"A to Z of SUDOKU"
Narendra Jussein, Ecole des Mines, Nantes, France

The science behind Sudoku...

Sudoku is a logic puzzle that has become a worldwidw phenomenon in the last few years: but where has it come from? How does it work? And what is the science behind sudoku - what are the rules for generating and solving grids?

Answer to all of these questions can be found in the A-Z of Sudoku. As its title suggests, this book provides a "one stop shop" on sudoku, covering the history of the puzzle, izs development and growth in the world's media, before moving on to the mathematics of sudoku and various techniques that can be used to solve grids by hand.

Next, the essentials of software development relating to sudoku are presenred along with the recent branch of computer science devoted to solving such problems: constraint programming, showing how the priniple behind solving sudoku grids can be used in other contexts. Finally, the book concludes with a large number of grids ranging in difficulty from "very easy" to expert which the reader can use to apply the techniques they have acquired from the book in a practical context.

Those interested finding out more about the theory behind sudoku, its origins, it applications in other fields and (of course) how to improve their ability to solve it will find this book is must-read.
...

January 2007 184 pages

[ГБ]

сложность не зависит от количества проставленных цифр.

Добавлено спустя 2 часа 33 минуты 45 секунд:

для Lion: "сложное" судоку вовсе не сложное, я его разгадала за 20 минут без подборов вариантов.Настоящие сложные судоку обязательно содержат "ловушки", когда в нескольких клетках получается несколько вариантов, и тогда нужно идти путем подбора до тупиков.

[Dan_Te]

ГБ писал(а):

сложность не зависит от количества проставленных цифр.

Очень спорный тезис. Можно ли назвать сложным судоку, в котором проставлено 80 цифр из 81?

[ГБ]

Спорность тезиса о том, зависит ли сложность судоку от количества проставленных цифр, легко проверить. Попробуйте решить судоку, названный Lion достаточно сложным (в нем проставлено всего 22 цифры) и судоку, названный "наш ответ Чемберлену" (в нем проставлено 27 цифр). Первое решается элементарно, со вторым надо помучиться.

Добавлено спустя 6 минут 52 секунды:

судоку Lion решается без перебора вариантов, без всяких ответвлений.

Добавлено спустя 22 минуты 45 секунд:

Насчет какуро: там вовсе не нужен перебор, и принцип такой же как в судоку. На мой взгляд, какуро даже интереснее, поскольку там больше вариантов.

[Lion]

Ну что ж, ГБ, а вот это тоже решите без перебора вариантов?

$$\begin{array}{ccc|ccc|ccc} *&*&*&*&*&*&*&2&1\\ 4&*&*&6&*&*&*&*&*\\ *&*&*&*&*&*&*&*&*\\ \hline *&*&*&*&1&2&9&*&*\\ 7&*&6&*&*&*&*&*&2\\ *&*&*&*&3&*&*&*&*\\ \hline 5&1&*&*&*&*&*&3&*\\ *&*&*&8&*&7&6&*&*\\ *&2&*&*&*&*&*&*&*\\\end{pmatrix}$$

[ГБ]

[quote="Lion"]Ну что ж, ГБ, а вот это тоже решите без перебора вариантов?

Решили, это не сложно.

[ГБ]

кто-нибудь входит в другие форумы любителей судоку?

[незваный гость]

Lion писал(а):

Ну что ж, ГБ, а вот это тоже решите без перебора вариантов?

Да, это тоже решается. Lion, большое спасибо! Изящная, хотя и не очень сложная судоку. Я уверен, что на ее композицию ушло заметное количество усилий.

P.S. Я готов привести ход решения без перебора, если это интересно кому-либо.

P.P.S. Перебор — с моей точки зрения скорее ухудшает судоку. Существуют беспереборные сложные судоку, требующие тонкого логического анализа. Хотя, если задуматься: любое правило решения в судоку — это проделанный доказательный частичный скрытый перебор.

[ГБ]

согласна, что лучшие судоку - без явных переборов.

[geomath]

Сегодня в метро видел, как судоку разгадывает немолодой мужчина, по виду вполне возможно, что доктор наук. В начальной расстановке у него 24 цифры и, что необычно, два квадрата из девяти - пустые. Не знаю, сложная эта судоку или, наоборот, очень простая, но непохоже, судя по скорости, что он ее разгадает даже за час... И хочу спросить, какое максимальное число пустых квадратов может быть в судоку? Два я вот видел. Три наверное тоже может быть. А больше может быть?

[ГБ]

кто может подсказать, что такое симметрия и ассиметрия в судоку?