Как система решает какуро
Для примера рассмотрим такую простую задачу. В ней всего 44 белых клетки и полный перебор состоит из 44! вариантов.
Вот таким числом записывается это количество: 2 658 271 574 788 448 768 043 625 811 014 615 890 319 638 528 000 000 000.
Даже, если ваш компьютер будет рассматривать по 24000000000 позиций в секунду (а примерно столько элементарных операций в секунду, таких как сложение, он может выполнять на 8 ядрах), то процесс поиска займет порядка 35 122 182 780 373 340 098 665 358 783 276 994 веков.
Очевидно, что такой алгоритм не подходит и его нужно значительно ускорить, ведь даже человеку с небольшим опытом решения этих задач для этой потребуется около 5 минут. Значит, программа должна вести себя подобно решающему.
Очевидно, что в верхней строке рядом с восьмёркой должна стоять цифра 7. Но для того, что бы это `понял` компьютер надо провести множество подготовительных операций. Формально, мы преобразуем какуро к системе уравнений, решение которой состоит из натуральных чисел до 10, с множеством ограничений в виде неравенств (ведь в каждом блоке повторы не допускаются).
Начнем перебирать черные клетки поля и если в них есть значения, то составлять систему. Для первой строки получим: bb+bc=15; be+bf=5; bh+8=15. И так далее, для всех строк и столбцов. Система получается достаточно большой, но на это требуется значительно меньше секунды.
Уже очевидно, что для того, что бы этот алгоритм `начал решать`, должно быть корректно задано условие задачи.
В реальности структура хранения несколько другая и список переменных и их сумма хранится раздельно, поэтому bh+8=15 не будет, а система просто вычтет 8 из правой части и получится bh=7. (Кстати, b - вторая строка; h - 8 столбец).
После составления такой системы уравнений, есть вероятность получить новые значения и убрать лишние строки. Для человека такой шаг элементарен и очевиден. Т.к. алгоритм уже приблизился к решению, имеет смысл его повторить, но перед этим присвоить в систему найденные значения.
Из предпоследнего столбца в системе существовала запись bh+ch=13. bh уже найдено, поэтому из этой строки его можно вычесть. Из левой части будет вычтено bh (фактически убрано из массива переменных), а из правой его значение - 7. Следовательно ch=6 (ch - цифра под семёркой).
К сожалению, указанных действий недостаточно для решения головоломки, если в ней изначально не определено никаких цифр.
Значит, алгоритм надо усовершенствовать.
Для каждой клетки имеет смысл хранить список её возможных значений. Изначально считаем, что в ней может быть любое число от 1 до 9. Будем последовательно исключать допустимые значения, обходя белые клетки. Критериев исключения немного.
Очевидно, что надо действовать по правилам и исключить возможные значения, если они уже встречаются в соответствующих блоках (вертикальном и горизонтальном).
Если сумма клеток четная, то можно исключить из допустимых половину суммы.
Есть критерии и сложнее. Допустимые значения можно ограничить сверху. Например, если сумма четырех клеток равна 12, то даже если в трёх будут цифры 1,2 и 3 (сумма 6) для четвертой (как и для всего ряда) уже нельзя использовать значения большее 6.
Аналогично и ограничение снизу. Тоже простой пример - сумма трёх клеток (алгоритм, конечно, рассмартивает систему, например zw+zy+zz=20) равна 20, а значит если мы будет использовать максимумы 8 и 9 (сумма 17), то цифр 1 и 2 недостаточно, а значит они недопустимы в этом блоке.
После исключения возможных вариантов может остаться одно допустимое значение. Оно и будет размещено в этой клетке. Если вариантов не осталось - в постановке задачи точно ошибка.
Алгоритм можно усложнить. Если в одном блоке две клетки могут иметь только два одинаковых значения, следует, что эти значения будут находится в них. А значит они не могут быть в других клетках этого блока.
Вариантов развития простых проверок множество и пока они не приводят к ресурсоемкой рекурсии, то будут ускорять решение и количество решаемых головоломок. Для усовершенствования необходимо добавить обнаружение неправильного условия.
В конце система будет либо решена, либо алгоритм перестанет вносить изменения в ситуацию - не изменяется ни система, ни допустимые значения - тупик. Возникает он, например, если какуро имеет несколько решений или требуется делать предположение в возможном значении, и если вариант окажется тупиковым - исключать его.
К этому моменту имеется алгоритм, который не допускает предположений и пытается решить головоломку без рекурсии, причем размер потребляемой памяти точно ограничен небольшими значениями (состояние доски, система, список допустимых значений клеток).
Продолжим. Переберем все варианты допустимых значений клеток, последовательно подставляя значения и применим к новому теоретическому состоянию предудущий алгоритм. Если решение вызовет противоречие, то выбранной цифры не может быть на этом месте. Тем самым, вероятно, будут исключены недопустимые варианты.
Существуют сложные какуро, для которых этих операций недостаточно, и требуется сделать два или более предложений (рекурсия). В этом случае, время решения и потребляемую память предсказать уже невозможно (все зависит от задачи).
Можно просто составить задачу (некорректную, т.к. имеет более одного решения), при анализе которой точно потребуется рекурсия. Усложнить ещё просто.
Естественно, при своей реализации можно не ограничивать предположения одним уровнем и предусмотреть дополнительные специфичные ситуации.
Реализованный на этом сайте алгоритм решения пока нигде не опубликован и никому не присылается. Описано далеко не все и очень кратко. Выбор структур данных и реализация зависит от языка программирования. Спасибо за понимание.
P.S. В задачах из печатных изданий есть ошибки. Бывает, что цифры поля, указанные в задании, отличаются от опубликованных в ответах.
Как решает и почему не решает
 
 
   
 
 
Яндекс.Метрика