Решение головоломок Какуро

Question

Вот хороший пример для размышления:

http://en.wikipedia.org/wiki/Kakuro

Я пытаюсь сделать решатель для этой игры. Делопроизводство завершено (чтение исходного файла с переменным числом столбцов и строк. Предполагается, что входной файл соответствует правилам игры, поэтому игра всегда решаема. Не торопитесь, чтобы прочитать правила игры.

Я позаботился о структуре данных, которая, я думаю, подойдет лучше всего:

struct aSquare { int verticalSum; int horizontalSum; int value; }

И сделал «массив» из них динамически для работы. Я сделал так, чтобы черные квадраты имели значение -1, а белые квадраты (фактические квадраты решения) инициализировались в 0. Вы также можете легко получить положение каждой структуры aSquare из массива, не нужно создавать для нее дополнительные поля структуры .

Теперь алгоритм ... Как в мире я примирю все эти суммы и найду общий способ, который решит все типы сеток. Я боролся с этим весь день безрезультатно.

Помощь приветствуется, веселитесь!

* РЕДАКТИРОВАТЬ: я только что понял, что фактическая ссылка, которую я разместил, содержит несколько советов относительно методов решения. Я все еще буду следить за тем, что придут люди.

Answer 1

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

• Google or-tools / Python: http://www.hakank.org/google_or_tools/kakuro.py
• Комета: http://www.hakank.org/comet/kakuro.co
• MiniZinc: http://www.hakank.org/minizinc/kakuro.mzn
• SICStus: http://www.hakank.org/sicstus/kakuro.pl
• ECLiPSe: http://www.hakank.org/eclipse/kakuro.ecl
• Gecode: http://www.hakank.org/gecode/kakuro.cpp
• Google or-tools / C #: http://hakank.org/google_or_tools/kakuro.cs
• Программирование набора ответов: http://hakank.org/asp/kakuro.lp

Редактировать: Добавлено Google or-tools / C # и Программирование набора ответов.

Answer 2

Простой брутфорс для Судоку занимает миллисекунды, поэтому вам не нужно беспокоиться о реализации какой-либо специальной тактики. Я думаю, что в случае Какуро это будет то же самое. Простой алгоритм:

def solve(kakuro):
    if kakuro has no empty fields:
        print kakuro
        stop.
    else:
        position = pick a position
        values = [calculate possible legal values for that field]
        for value in values:
            kakuro[position] = value
            solve(kakuro)
        kakuro[position] = None # unset after trying all possibilities

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

В любом случае, это, вероятно, будет проще всего реализовать, поэтому попробуйте и ищите более сложные решатели, только если этот не будет работать. (На самом деле это один из простейших решателей программирования с ограничениями; реальные решатели CP, конечно, намного сложнее).

Answer 3

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

http://en.wikipedia.org/wiki/Constraint_programming

Answer 4

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

В любом случае использование таблицы с наиболее определенными комбинациями наверняка будет полезно (например, http://www.enigmoteka.com/Kakuro%20Cheatsheet.pdf)

Answer 5

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

Answer 6

Это прямолинейная линейная алгебра, для решения которой используются векторные / матричные методы.

[править - отвечая на комментарии]

a + b + 0 + d + 0  = n1
0 + b + c + 0 + e  = n2
a + 0 + c + 0 + 0  = n3
a + b + c + 0 + e  = n4
a + 0 + c + d + 0  = n5

Выше преобразуется в матрицу, и, сложив и вычтя кратные строки, вы получите:

a 0 0 0 0 na
0 b 0 0 0 nb
0 0 c 0 0 nc
0 0 0 d 0 nd
0 0 0 0 e ne

Нет комбинаторики, все остаются целыми числами.