Это просто решение ограничений.
Если у вас есть доска судоку, то для каждой ячейки (i, j) у вас есть следующие ограничения:
board[i, j] in [1, 2, 3, 4, 5, 6, 7, 8, 9]
for each cell (a, j) where i != a: board[a, j] != board[i, j]
for each cell (i, b) where j != b: board[i, b] != board[i, j]
Для конкретных ячеек вы уже знаете их значение. Это действительно просто другое ограничение:
board[c1, c2] == 7
Вот и все. Средство проверки грубой силы может просто перебрать все возможные способы заполнения ячеек доски (особенно обращая внимание на первое ограничение) и проверить, выполняются ли эти ограничения. Если они все держат за эту заливку, то можно выводить доску. В противном случае это продолжается.
Если теперь вы разрешите неравенства для определенных позиций, вы можете использовать тот же самый алгоритм грубой силы. Это просто новая проверка, которую он должен сделать, прежде чем сказать, что доска заполнена правильно:
2 <= board[c3, c4] < 8
Это легко с помощью грубой силы, но также довольно просто с языком логического программирования, таким как Prolog, или библиотекой программирования с ограничениями, такой как Numberjack.
Вот версии всех вышеперечисленных ограничений в Numberjack (в порядке появления):
board[i, j] = Variable(1, 9)
# ... need to define all the board before you execute the following:
for a in xrange(1, 10):
model.add(board[a, j] != board[i, j])
model.add(board[i, a] != board[i, j])
model.add(board[c1, c2] == 7)
model.add(board[c3, c4] < 8)
model.add(board[c3, c4] >= 2)
Это не идиоматично для реального использования решателя ограничений. В реальной жизни вместо того, чтобы указывать != по отдельности, вы бы использовали ограничение «Все они разные», AllDiff и т. д. Но Вы получаете идею.
person
Devin Jeanpierre
schedule
12.04.2011
