Судоку

[geomath]

Вот все хочу спросить. Что вы думаете о судоку? Это интересный объект математически? Конечно, чтобы решать задачи судоку не обязательно знать даже арифметику. Ну а все же?

В метро нередко можно увидеть, как люди разгадывают судоку. Что меня больше всего поражает - это что они делают это шариковой ручкой! Хотя я в общем не любитель головоломок, но специально попробовал разгадать одну судоку. Потратил не менее часа. Да, действительно, поначалу можно вставлять цифры и шариковой ручкой, но под конец мне все-таки пришлось вписывать цифры (по две) карандашом, чтобы потом их можно было стереть. Или я неправ?

http://www.sciam.ru/2006/12/mathemarics.shtml
http://www.sudoku.com/

[Lion]

geomath писал(а):

Хотя я в общем не любитель головоломок, но специально попробовал разгадать одну судоку. Потратил не менее часа.

Это с непривычки. Поверьте, 99% всех судоку разгадывается за 5 минут. Если хотите. я могу привести действительно сложные судоку.

[geomath]

Lion писал(а):

Поверьте, 99% всех судоку разгадывается за 5 минут. Если хотите. я могу привести действительно сложные судоку.

Получается, никакого математического интереса судоку не представляет? Давайте, приводите действительно сложную судоку, пусть народ поупражняется. А для решения на компьютере она тоже сложна?

[Lion]

geomath писал(а):

Получается, никакого математического интереса судоку не представляет? Давайте, приводите действительно сложную судоку, пусть народ поупражняется. А для решения на компьютере она тоже сложна?

Скорее всего --- нет. Можно придумать конкретный алгоритм, который в 99 % случаев не использует перебор вообще.
Привожу пример достаточно сложного судоку:

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

Насчет решения на компьютере: один мой друг утверждает, что он написал макрос для решения судоку. Удивительно, что когда он его тестировал, достаточно простые судоку он не решал, а вот сложные --- решал, причем очень быстро.
Данную судоку мы не тестировали. Вообще, интересно, решит ли ее компьютер. В журнале, где я ее взял, она опубликована как "Судоку для гениев" (!). Утверждается, что такие сложные судоку может решить только 3% населения нашей планеты. Так что если оно Вам покорится, можете смело считать себя гением!

Добавлено спустя 21 минуту 30 секунд:

Да, наверное, насчет математики я не совсем прав. Вот придумал несколько интересных задач, предлагаю желающим попробовать решить.

1. Придумать алгоритм, который будет строить судоку.
2. Каково минимальное количество цифр, необходимое для того, чтобы соответствующая судоку имела единственное решение?

Насколько мне известно, данные задачи пока никем не решены.

[Dialectic]

А не раскажите ли- как играть то в неё?
Что сделать нужно?

[Capella]

Dialectic

Нужно так расставить числа, чтобы в каждом столбце и строчке не было повторов.

[PAV]

Не только. Числа должны быть от 1 до 9. И еще, повторов не должно быть не только в строке или столбце, но и в каждом естественном квадрате $3\times3$, которых 9 штук.

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

Lion писал(а):

Привожу пример достаточно сложного судоку:

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

Я добавил в код линейки, отделяющие указанные квадраты, в которых также не должно быть повторов

[cepesh]

Lion
http://www.sudokusolver.co.uk/ решил, но использовались догадки

Добавлено спустя 14 минут 21 секунду:

офигенная штука
http://www.scanraid.com/sudoku.htm

В вашей задаче 75 решений!
http://www.scanraid.com/S/WebSudoku.dll ... 0910030000

[Brukvalub]

geomath писал(а):

Что вы думаете о судоку? Это интересный объект математически? Конечно, чтобы решать задачи судоку не обязательно знать даже арифметику. Ну а все же?

Интересно было бы, на мой взгляд, оценить сверху и снизу сложность алгоритма решения судоку (речь я веду о нетривиальной оценке с использованием алгоритма,заранее отбрасывающего заведомо неприемлемые варианты, а не о количестве вариантов при прямом переборе всех, даже явно невозможных, случаев)

[Lion]

cepesh писал(а):

В вашей задаче 75 решений!
http://www.scanraid.com/S/WebSudoku.dll ... 0910030000

Решение одно, просто Вы пропустили цифру "2" в правом нижнем квадрате.

[geomath]

Capella писал(а):

Нужно так расставить числа, чтобы в каждом столбце и строчке не было повторов.

PAV писал(а):

Не только. Числа должны быть от 1 до 9. И еще, повторов не должно быть не только в строке или столбце, но и в каждом естественном квадрате, которых 9 штук.

Это означает, что в зачатке у судоку есть фрактальные свойства. Интересно, а размерность этого судоку-фрактала можно подсчитать?

[Lion]

geomath писал(а):

Это означает, что в зачатке у судоку есть фрактальные свойства. Интересно, а размерность этого судоку-фрактала можно подсчитать?

Но все-таки, судоку --- это не фрактал. Что тогда Вы понимаете под его "размерностью"?

[geomath]

Lion писал(а):

Но все-таки, судоку --- это не фрактал. Что тогда Вы понимаете под его "размерностью"?

Ну, я не знаю. Возможно, размерность судоку в целом равна 2, ибо если этими судоку (заполненными) обклеить кубик Рубика, разрезать и начать вращать... то полученная головоломка, наверное, будет размерности 3.

А может, удастся сделать из судоку действительно фрактал...

Другая идея. Допустим, что время, затраченное на решение судоку и неким образом усредненное, окажется обратно пропорциональным n-ой степени начального количества проставленных в судоку цифр. Тогда размерность судоку я бы положил равной n.

[geomath]

А еще судоку напоминает мне рифмованные стихи.

[geomath]

Японского языка я не знаю, но думаю, что любовь японцев к судоку как-то связана с их системой стихосложения. Опять же мне трудно судить о том, как японцы воспринимают свои стихи и какими эти стихи могут быть вообще. Но вот что касается японского слогового стихосложения, то классические его формы я знаю две: хокку (хайку) и танка. Хокку - это трехстишие (5 + 7 + 5 слогов: в первой строчке 5 слогов, во второй - 7, в третьей - снова 5), а танка - это пятистишие (5 + 7 + 5 + 7 + 7 слогов). Вот два примера О. Черемшановой. Это не японская поэзия, но в ее стиле. Да и вряд ли русская.

(5) Знай! Я - ствол дуба
(7) Четырехсотлетнего.
(5) Любя не сломить!

(5) Не смейте думать,
(7) Что люблю, потому что
(5) Смотрю вам в зрачки.
(7) Зеркала нет. Я смотрю,
(7) Чтоб поправить прическу...

Не знаю, можно ли сочинять стихи в стиле судоку? И какая головоломка была бы сродни русскому стихосложению?