В колонках играет - Yoko Kanno - Want it All Back

запись больше для себя

всю субботу и воскресение разрабатывал программу, которая перебирает все возможные варианты решения задачи судоку. поле может быть незаполненным, тогда находятся вообще все варианты решения. Правила разнородности применяются не только в отношении строк, столбцов и внутренних квадратов, но и вообще могут применяться в отношении произвольных фигур, главное соблюсти их размеры.
так же программка по найденному решению находит минимально решенное поле, которое однозначно решается в изначальное заполненное поле.
Маски (правила разнородности) подгружаются из картинок.
Задачи судоку, которые приводят в сборниках, решает как делать нефиг=)
Только вот полный перебор всех возможных вариантов можно производить только до поля 6х6 (вертикали, горизонтали и кастомная маска), и то кастомная маска должна быть сбаллансированной с первыми двумя (иначе решений будет либо очень мало, либо много, и искаться они будут минутами). Для чистых полей 7х7 производить перебор уже бессмысленно.
Есть вариант, когда первичное заполнение программа выполняет рендомом (первичное расположение раскрытых клеточек не нарушает целостность модели) для перебора возможных вариантов для размеров более высоких порядков, но там есть свой трейд-офф - слишком большое кол-во первоначально заполненных клеточек может убить возможность решения сразу же, а слишком маленькое заставит перебирать решения гораздо дольше. Иногда во время перебора машина виснет наглухо >_>
То, как подберёшь маски, тоже влияет на быстроту перебора и возможность решения в случае случайного первоначального заполнения.
Осталось подумать насчет другого алгоритма перебора. Опираться не на поклеточную валидацию, а погрупповую; заполнять группу, потом смотреть.

впереди - поддержка кастомной формы поля. Если только эксперименты с масками не покажут, что самое правильное и сбаллансированное судоку уже придумано и давно используется=)))))))

Вопщем, моск в эти выходные не высох=)