Судоку

[venco]

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

[Sonic86]

venco
Понятно, в говорите о переборе, видимо в глубину. Я вот только Вашу фразу про сложные судоку наверное рассмотрю как определение сложного судоку. Тогда надо еще доказать, что сложные судоку существуют.
Пока (потом еще напишу подробнее) нам удалось продвинутся в решении судоку Liona без использования явного перебора. Мы для каждой клетки u можем ввести множество возможных цифр в ней H(u). Если уже не видно, куда ставить цифру на очередном шаге, то со всеми H(u) можно поработать примерно так же, как и просто с цифрами. Помогает аналог алгоритма А3, только для цифр: Пусть F1 и F2 - ограничения на множества M1 и M2, причем M1 - подмножество M2, тогда если цифра x лежит в одной из клеток М1, то она не лежит в клетках М2 и тогда для всех y из М2 цифру х можно исключить из H(y). Это помогает.

[Sonic86]

Дополнил алгоритм решения судоку:
Пусть $U = \{ u_1, ..., u_ k \}$ -множество клеток, $X = \{ x_1, ,,,, x_k \}$ - множество цифр, $U=X$ - ограничение. Разобьем $U$ на классы $U_1$ и $U_2$.
А4 - алгоритм А3 + следующий алгоритм.
Если известно, что некоторая цифра x, лежит в одной из ячеек $U_1$, то она не лежит ни в одной из ячеек $U_2$.
А5 - алгоритм А4 + следующий алгоритм.
1) $H=\bigcup\limits_{u_1 \in U_1}H(u_1) \wedge |H|=|U_1| \to (\forall h \in H)(\forall u_2 \in U_2) h \not \in H(u_2)$
2) $H=\bigcup\limits_{u_1 \in U_1}H(u_1)$, $T \subset H \wedge |T| = U_1 \to (\forall y \in H\T)(\forall u_2 \in U_2) y \not \in H(u_2)$
В итоге получаем алгоритм А5.
Хотя тяжело рассуждать по А5 без вычисления всех $H(u)$, человек его использует, хотя бы в частных случаях. С помощью А5 удалось продвинуться в решении 1-о судоку (Lion) и 2-о (Наш ответ Чемберлену). Однако, при решении 1-о судоку Lionа мы попадаем перед самым концом в ситуацию, где нельзя сделать ход даже с помощью А5, да и вообще без поиска в глубину (ну или метода от противного - то же самое) ничего не получается! То есть, если нельзя придумать непереборный алгоритм решения, то 1-е судоку - сложное в смысле venco. Мне очень интересно, тут народ его решил и неоднократно. Наверняка при решении все напоролись в конце на то же место, что и я. Можете привести Ваши рассуждения? Может быть - они не переборные? Если нужно, полученную ситуацию могу нарисовать.

[Nik_Svan]

geomath в сообщении #50061 писал(а):

Вот все хочу спросить. Что вы думаете о судоку?

От нечего делать лучше гадать на кофейной гуще.

[Sonic86]

Купил несколько этих книжек с судоку, которые продают в печати. Прорешал алгоритмом А5 около 20 судоку разной степени сложности. У меня получилось следующее. Все судоку решились А5, причем иногда, когда задача имела несколько решений, с помощью А5 можно было найти все однозначно определенные цифры. Сложность судоку, определенная авторами, слабо "коррелирует" со сложностью решением А5. Мне вот по простоте мыслилась такая схема:
1. Средние судоку, решаемые А4 (т.е. простыми рассуждениями, без использования множеств допустимых значений).
2. Сложные судоку, не решаемые А4, но решаемые А5 (с использованием множеств допустимых значений).
3. Очень сложные судоку (типа Liona и "Наш ответ Чемберлену"), которые А5 не решаются, но решаются (ессно) перебором.
Все попавшиеся мне судоку были из классов 1 и 2, но автором они были независимо от этих классов разнесены в другие классы "4*", "5*", "Эксперт", "Мега-судоку" и т.п. Лично мне это непонятно. Впрочем, к классу "Эксперт" относились обычно задачи, имеющие более 1 решения, и в этом же классе не было судоку класса 1. Странная у составителей квалификация, хотя конечно, задачи с несколькими решениями не решаются А5. Видимо судоку класса 3 достаточно редки, как редки некоторые представители NP-полных задач, не решаемых жадными алгоритмами.

[mserg]

Общий алгоритм решения задач, подобных Судоки, был разработан месье Лорьером в начале 70-х годов (см. книгу «Системы искусственного интеллекта», глава «Информационная система ALICE»).
Суть его состоит в следующем. Задача представляется в виде описания конечных дискретных переменных и в виде набора ограничений. Система решения задач ALICE содержала в себе систему считывания условий задачи, систему ветвления (перебора) и набор полиномиальных алгоритмов, которые позволяют сокращать перебор. После считывания задачи система ALICE автоматически (!) применяет полиномиальные алгоритмы для удаления недопустимых значений переменных (см. в Интернете «Распространение ограничений», «Метод вперед-назад», «Интервальный анализ»). Если обнаружено противоречие – задача не имеет решения. Если все переменные зафиксированы – найдено единственное решение. Если есть незафиксированные переменные – нужно ветвиться (делать шаг перебора): делается ветвление и для каждой ветки начинается все сначала.
Т.е. никакого антагонизма между «перебором» и «логическим решением» нет в природе. Просто, в силу отсталости нашего образования, под «логическим методом решения задач» неокрепшие умы называют систему сжатия доменов переменных и систему распространения ограничений. Если в системе решения задачи есть подходящие полиномиальные алгоритмы, то решение находится легко. Если в системе мало «подходящих» алгоритмов - доля перебора в решении задачи растет. Отсюда, кстати следует бессмысленность NP-классификации, т.к. важен не столько сам факт экспоненциального нарастания сложности, сколько сама доля перебора в решении задачи.

Сам я непосредственно участвую в разработке системы Quick NP, в которой можно решить многие задачи Судоки. Предложенные в обсуждения задачи с 81-м числом имеют точно по одному решению. Quick NP использует 3 и 6 узлов дерева поиска соответственно чтобы полностью решить задачи. Если не считать неудачные узлы ветвления (сразу после ветвления становится ясно, что есть противоречие), то можно сказать, что Quick NP решает эти задачи без перебора. Т.е. если не считать за узел перебора действий типа «переменная x не может равняться a, так как получаем противоречие», то Quick NP обходится полностью без перебора. Ниже приведено формальное описание задачи на NP-языке, который используется Quick NP.

Project Sudoki9

Module Main
Field Lines() As Integer

Con Ins As ' Создание клеток
__ForAll(i In Lines, Append(Check, Me:i, Dig:Lines(i)))

Con InsFigs As ' Создание столбцов, строк и квадратов
__ForAll(i In {1..9},
____Append(Row, Me:i) And Append(Col, Me:i) And Append(Square, Me:i))


Class Row
Var theChecks{} As Integer = Union(c In Check, c.y=Me, c)
Con Injs As Inj(c In theChecks, Check(c).d) ' Цифры в строках уникальны


Class Col
Var theChecks{} As Integer = Union(c In Check, c.x=Me, c)
Con Injs As Inj(c In theChecks, Check(c).d) ' Цифры в стобцах уникальны


Class Square
Var xStart As Integer = (Me-1) Mod 3 * 3 + 1
Var yStart As Integer = (Me-1) \ 3 * 3 + 1
Var theChecks{} As Integer =
__Union(c In Check, Between(c.x, xStart, xStart+2) And
____Between(c.y, yStart, yStart+2), c)
Con Injs As Inj(c In theChecks, Check(c).d) ' Цифры в квадратах уникальны


Class Check
Field Dig As Integer
Var x As Integer = Me - 9*(y-1) ' Координата x клетки
Var y As Integer = (Me - 1) \ 9 + 1 ' Координата y клетки
Var d As If(Dig=0, {1..9}, {Dig}) ' Переменная цифры клетки
Con Save As Store(x, y, d)


Data $InFile
Main(Lines)
__1, {8,3,0, 6,0,0, 0,0,1,
______0,0,6, 0,3,0, 0,8,0,
______0,0,1, 8,0,0, 0,6,0,

______0,0,0, 9,0,0, 0,4,0,
______0,0,3, 0,7,0, 2,0,0,
______0,7,0, 0,0,5, 0,0,0,

______0,1,0, 0,0,4, 6,0,0,
______0,5,0, 0,9,0, 8,0,0,
______9,0,0, 0,0,6, 0,2,3}
End

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

Ниже приведено описание задачи ХИТОРИ на NP-языке
Project Hitory

Module Main
Field Size As Integer

Con InsCols As ForAll(c In {1..Size}, Append(Col, Me:c))

Con StartConn As ' Начальная клетка поиска связности
__If(Check(1).Used, Check(1).Conn, Check(2).Conn)

Class Row
Field Cols() As Integer
Ref theChecks{} As Check.theRow

Con InsChecks As ' Создание матрицы
__ForAll(c In Cols, Append(Check, theRow:Me, theCol:c, v:Cols(c)))

Con Unique As ' Не более одной уникального числа в строке
__ForAll(i In {1..Size},
____Sum(c In theChecks, c.v=i) >= 2 ==>
______Sum(c In theChecks, c.v=i, c.Used) <= 1)

Class Col
Ref theChecks{} As Check.theCol
Con Unique As
__ForAll(i In {1..Size}, ' Не более одного уникального числа в столбце
____Sum(c In theChecks, c.v=i) >= 2 ==>
______Sum(c In theChecks, c.v=i, c.Used) <= 1)

Class Check
Field v As Integer ' Число в клетке
Var Used As Boolean ' Истино, если клетка не вычеркивается
Var Conn As Boolean ' Переменная связности
Ref theCol As Col.theChecks ' Колонка
Ref theRow As Row.theChecks ' Столбец
Var Neibs{} As Integer = ' Соседние клетки
__If(theCol>1, {Me-1}, {}) Union If(theCol<Size, {Me+1},{})
____Union If(theRow>1, {Me-Size}, {}) Union If(theRow<Size, {Me+Size}, {})
Con EmptyNoConn As ' Не вычеркивать соседние клетки
__ForAll(c In Neibs, c < Me ==> Check(c).Used+Used >= 1)
Con Conns As ' Обеспечение связности
__Def(Conn) And Dep(Conn) And
____If(Used, ForAll(i In Neibs, Check(i).Conn ==> Conn), Not Conn)
Con Save As Store(theCol, theRow, Used)


Data $InFile
Main(Size)
__1, 15
End

Row(Cols)
___1, { 9, 3, 6, 4, 8, 8, 15, 6, 12, 1, 5, 2, 12, 3, 15 }
___2, { 13, 4, 4, 5, 6, 10, 13, 14, 7, 14, 2, 14, 1, 11, 12 }
___3, { 7, 9, 5, 15, 11, 9, 1, 10, 9, 3, 12, 4, 6, 5, 8 }
___4, { 3, 4, 9, 7, 14, 7, 13, 12, 2, 6, 6, 13, 4, 10, 8 }
___5, { 12, 15, 8, 13, 7, 5, 6, 11, 5, 14, 3, 13, 5, 9, 2 }
___6, { 14, 6, 12, 4, 2, 9, 4, 4, 3, 15, 6, 8, 7, 13, 10 }
___7, { 11, 2, 4, 6, 15, 15, 2, 1, 5, 9, 8, 4, 10, 3, 13 }
___8, { 6, 14, 1, 11, 5, 12, 8, 3, 8, 10, 10, 15, 4, 2, 4 }
___9, { 8, 12, 8, 10, 7, 2, 11, 6, 14, 4, 10, 9, 15, 5, 7 }
__10, { 5, 13, 15, 3, 13, 3, 14, 10, 6, 12, 7, 12, 11, 1, 4 }
__11, { 6, 10, 3, 1, 8, 4, 7, 2, 11, 7, 14, 7, 7, 15, 4 }
__12, { 2, 8, 7, 12, 1, 4, 5, 9, 13, 13, 15, 13, 14, 8, 3 }
__13, { 12, 8, 4, 1, 13, 14, 12, 7, 13, 5, 11, 3, 14, 9, 9 }
__14, { 10, 4, 14, 10, 9, 6, 3, 7, 1, 7, 4, 6, 2, 7, 15 }
__15, { 2, 7, 2, 9, 12, 14, 8, 13, 10, 6, 4, 14, 3, 13, 11 }
End


Система Quick NP, используя 1735 узлов дерева поиска, обнаружила 31 решение. Ниже приведено одно из них (а также набор удаляемых пар, если я неправильно что-то набил в матрице):

Row(Cols)
   1, {  9,   ,  6,  4,   ,  8, 15,   , 12,  1,  5,  2,   ,  3,    }
   2, { 13,  4,   ,  5,  6, 10,   , 14,  7,   ,  2,   ,  1, 11, 12 }
   3, {  7,  9,  5, 15, 11,   ,  1, 10,   ,  3, 12,  4,  6,   ,  8 }
   4, {  3,   ,  9,   , 14,  7,   , 12,  2,   ,  6, 13,  4, 10,    }
   5, {   , 15,   , 13,  7,   ,  6, 11,   , 14,  3,   ,  5,   ,  2 }
   6, { 14,  6, 12,   ,  2,  9,  4,   ,  3, 15,   ,  8,  7, 13, 10 }
   7, { 11,   ,  4,  6,   , 15,  2,  1,   ,  9,  8,   , 10,   , 13 }
   8, {   , 14,  1, 11,  5, 12,   ,  3,  8,   , 10, 15,   ,  2,    }
   9, {  8, 12,   , 10,   ,  2, 11,  6, 14,  4,   ,  9, 15,  5,  7 }
  10, {  5,   , 15,  3, 13,   , 14,   ,  6, 12,  7,   , 11,  1,  4 }
  11, {  6, 10,  3,   ,  8,  4,   ,  2, 11,   , 14,  7,   , 15,    }
  12, {  2,   ,  7, 12,  1,   ,  5,  9,   , 13, 15,   , 14,  8,  3 }
  13, { 12,  8,   ,  1,   , 14,   ,  7, 13,  5, 11,  3,   ,  9,    }
  14, { 10,   , 14,   ,  9,  6,  3,   ,  1,   ,  4,   ,  2,  7, 15 }
  15, {   ,  7,  2,  9, 12,   ,  8, 13, 10,  6,   , 14,  3,   , 11 } 
End

Check(theCol, theRow)
  2, 1
  5, 1
  8, 1
  13, 1
  15, 1
  3, 2
  7, 2
  10, 2
  12, 2
  6, 3
  9, 3
  14, 3
  2, 4
  4, 4
  7, 4
  10, 4
  15, 4
  1, 5
  3, 5
  6, 5
  9, 5
  12, 5
  14, 5
  4, 6
  8, 6
  11, 6
  2, 7
  5, 7
  9, 7
  12, 7
  14, 7
  1, 8
  7, 8
  10, 8
  13, 8
  15, 8
  3, 9
  5, 9
  11, 9
  2, 10
  6, 10
  8, 10
  12, 10
  4, 11
  7, 11
  10, 11
  13, 11
  15, 11
  2, 12
  6, 12
  9, 12
  12, 12
  3, 13
  5, 13
  7, 13
  13, 13
  15, 13
  2, 14
  4, 14
  8, 14
  10, 14
  12, 14
  1, 15
  6, 15
  11, 15
  14, 15
End 

Технологии на месте не стоят, а многих из обсуждавшихся здесь проблем/вопросов, не существует в природе уже десятки лет.

[iig]

Судоку - один из разделов абстрактной алгебры, а конкрентно - теория дискретных квазигрупп.
У профессионалов давно истоптана, изотопна.. (забыл) лупе.
Если интересно, могу дать ссылки, там куча определений и теорем.
Я интересовался этим еще задолго до этих дурацких судоку и вовсе не для того, чтобы загадки делать и решать, а для классификации квазигрупп и луп.
Зачем - не стану объяснять, зайдите на мой сайт, но там пока намеки.
Мой интерес сейчас - непрерывные лупы, типа группы Ли меняются в пространстве.
Мой интерес к этому происходил не из бумажек, купленых в дороге, а из стремления свести геометрию ОТО к простым законам алгебры.

[PAV]

Математик составил самую сложную в мире головоломку-судоку

Цитата:

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

37-летний Арто Инкала уверен, что для решения его судоку самым азартным игрокам потребуется как минимум несколько дней...

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

[Joker_vD]

Не получилось разобраться в приведенных алгоритмах :(

Пришлось самому два придумать:

Итак, мы имеем лист с написанным ручкой судоку, карандаш, ластик и ручку.

Алгоритм №1.

Шаг 1. Для каждой пустой клетки:
а) пишем в ней карандашом все цифры от 1 до 9;
б) стираем те цифры, которые в строке/столбце/квадрате, которым принадлежит эта клетка, написаны ручкой.
Шаг 2. Для каждой клетки с ровно одной карандашной цифрой совершаем Х-процедуру:
а) стираем цифру и пишем ее в эту клетку уже ручкой;
б) стираем эту цифру из всех остальных клеток, находящихся в одной строке/столбце/квадрате с этой клеткой.

Алгоритм останавливается, когда в любой клетке либо написанная ручкой цифра, либо $\geq 2$ карандашных цифр.

Алгоритм №2. Предполагается, что алгоритм №1 уже проработал.

Шаг 1. Для каждого неполностью заполненного строки/столбца/квадрата:
а) для каждой цифры, не написанной в этой строке/столбце/квадрате ручкой:
i.) подсчитываем число клеток, в которых стоит записанная карандашом эта цифра
ii.) если есть ровно одна такая клетка, то совершаем с ней X-процедуру.

Алгоритм останавливается, когда в любой клетке либо написанная ручкой цифра, либо $\geq 2$ карандашных цифр, при этом в любой строке/столбце/квадрате любая карандашная цифра встречается не меньше, чем в двух клетках.

Так вот, это, с одной стороны, перебор... с другой, это все же не метод проб и откатов. Можно ли к приведенным выше алгоритмам добавить еще?

[venco]

Не только можно, но и нужно. Более-менее сложные Судоку не решаются только этим алгоритмом.
Если Вам не хочется связываться с откатом, то можно добавить такой пункт:
Шаг 3. если некоторое количество $n$ чисел из одного набора (строка/столбец/квадрат) могут находиться только в $n$ клетках этого набора, то другие числа из этих клеток можно стереть. Это обобщение Вашего Алгоритма 2 на группу чисел.

Многие Судоку можно будет решить с этим шагом, но особо сложные без проб и откатов не решить. А если реализовать пробы и откаты, то вышеприведённый Шаг 3 не обязателен.

[Joker_vD]

Этот "Шаг 3" надо в 1-м или во 2-м алгоритме делать? И что-то я не совсем его понял...

Это примерно так? "Выбираем строку/столбец/квадрат. Выбираем $n$ чисел, записанных там карандашом. Если число клеток, в которых встречается хотя бы одно из этих чисел, равно $n$, то во всех этих клетках стираем числа, отличные от выбранных".

[venco]

Joker_vD в сообщении #353527 писал(а):

Этот "Шаг 3" надо в 1-м или во 2-м алгоритме делать? И что-то я не совсем его понял...

В любом.
А вообще у нас алгоритм один - решение Судоку. А то что Вы написали - это, скорее, шаги.

Joker_vD в сообщении #353527 писал(а):

Это примерно так? "Выбираем строку/столбец/квадрат. Выбираем $n$ чисел, записанных там карандашом. Если число клеток, в которых встречается хотя бы одно из этих чисел, равно $n$, то во всех этих клетках стираем числа, отличные от выбранных".

Так.

[Joker_vD]

Хорошо, тогда что мы получим после этого шага? И почему этот шаг легален?

Стоп, а там разве не "Выбираем строку/столбец/квадрат. Выбираем $n$ чисел, записанных там карандашом. Если число клеток, в которых встречаются все эти числа, равно $n$, то во всех этих клетках стираем числа, отличные от выбранных" должно быть?

[Stevendall]

Lion в сообщении #50228 писал(а):

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

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

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

Ещё задачка:
Есть ли два судоку, которые невозможно перевести одно в другое ни перестановкой столбцов/строк, ни перестановкой групп столбцов/строк по три, ни поворотом, ни зеркальным отражением, ни взаимозаменой чисел.

Если таких двух судоку нет, то значит существует ОДНО ЕДИНСТВЕННОЕ судоку!

[bnovikov]

Вот статья о Судоку с точки зрения квазигрупп:

A. D. Keedwell. On Sudoku squares. Bull. Inst. Combin. Appl., v.50 (2007), 52–60.