|
Я прочел тут все, сам потренировался в решении судоку. Вот что у меня получилось (простые определения не привожу и формально тоже писать неохота).
1. Сложность судоку и алгоритмов его решения можно оценивать так. Пусть есть судоку С и алгоритм А, который позволяет его решить. Ходом в судоку назовем однозначное определение какой-либо цифры в какой-либо клетке. Состоянием судоку С назовем таблицу, получаемую из С в результате некоторой последовательности ходов. Тогда можно все состояния и ходы представить в виде ориентированного дерева с истоком С и стоком О - конечным состоянием С (оно одно)(дерево будет слоеное, так что расстояние от истока до стока по любому маршруту постоянно). У этого дерева можно найти среднее число степеней исходов из вершин - это и будет сложность судоку. Иначе говоря - среднее количество ходов, которые можно сделать при решении С. Найти такую сложность судоку сложнее, чем решить его. Можно также учесть количество элементарных шагов алгоритма А для хода - получится средняя взвешенная сумма. Если у алгоритмов А1 и А2 множества элементарных шагов совпадают, то оценивая сложность решения некоторого судоку С с помощью А1 и А2 и получая оценки S1 и S2, можно сравнивать эффективность алгоритмов А1 и А2. Усредняя по всевозможным судоку, можно определить, какой из алгоритмов эффективнее. Но эта задача, видимо, очень тяжелая, хотя сразу очевидно, что алгоритмы, которые использует человек будут эффективнее алгоритмов тупого полного перебора.
(Можно также рассматривать среднее числа шагов по всем маршрутам)
2. Хорошо бы придумать такой алгоритм решения судоку, чтобы он основывался на тех способов, которые использует человек, но решал бы любое судоку. В процессе решения нашел 3 простых алгоритма.
Обозначим горизонтали слева направо буквами a,b,c,...,h,i, а вертикали снизу вверх 1,2,...,9, клетки - парами буква-цифра (напр (g,5)=g5), ограничениями назовем В-,Г- и К-ограничения. В-ограничения - это условия вида {x1,x2,...,x9} = {1,2,...,9}, где x лежит в {a,b,...,i}. Г-ограничения - это условия вида {ax,bx,...,ix} = {1,2,...,9}, где x лежит в {1,2,...,9}. К-ограничения - условия по типу {a1,a2,a3,b1,b2,b3,c1,c2,c3}={1,2,...,9}. Каждому ограничению F взаимно-однозначно соответствует его вертикаль, горизонталь или квадрат - множество клеток M(F).
Алгоритм А1: берем любое ограничение F и цифру х, которой нет в заполненных клетках M(F). Если для всех незаполненных клеток k из M(F), кроме одной - u, подстановка х в k ведет к невыполнению какого-то другого ограничения F2, то в u должно стоять х. А1 на каждом ходе перебирает все 27 ограничений, и если хотя бы одни х и u найдены, то он его вставляет x в u и перебирает заново. А1 останавливается, если на очередном ходе х не был найден.
Думаю, что А1 доступен всем и 99% судоку, упомянутых Leon может быть решено им. Ни одно из 3-х судоку здесь написанных, решить по А1 у меня не получилось (хотя я мог ошибиться, считал вручную).
А2 у меня точно сформулировать не получилось. Смысл был в том, что возможны такие случаи, когда для того, чтобы исключить все клетки, кроме одной, куда мы хотим вставить х, для данного ограничения, достаточно знать не сами клетки, где тоже стоят х, а только их координаты. Но потом обнаружилось, что во всех таких случаях удается взять другое ограничение, рассмотрение которого по А1 ведет к тому же результату. То есть А1 и А2 получились эквиваленты (строго я, ессно, не доказывал).
А3 работает на каждом ходе как алгоритм А1 с последующим применением следующеих шагов. С учетом заполненных клеток ограничения F разбиваются на более мелкие ограничения F1, F2,..., а потом А1 применяется к ним. Тут проще на примере. Пусть а1=1, а2=2, а3 = 3, b1=4, b2=5, b3=6, g2=7, i2=8, остальные пусты (безразличны). Тогда К-ограничение принимает вид F:{c1,c2,c3}={7,8,9}, а ввиду g2=7, i2=8 оно разбивается на F1:{c1,c3}={7,8}, F2:{c2}={9}, к которым мы уже и будем применять А1. В данном примере, конечно, сразу c2=9, но это только в случае одно элементных множеств.
Очевидно, хотя бы на этом примере, что А3 не сводим к А1.
Достаточно ли А3 для решения любого судоку? - я не знаю. Хотя мне пока даже 3-е судоку здесь им решить не удается (вручную делал, мог ошибиться).
|
