Это просто решение ограничений.
Если у вас есть доска судоку, то для каждой ячейки (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 и т. Д. Но вы поняли.