Могут ли танцевальные ссылки быть применены к этому CSP?

Question

Может ли реализация Dancing Links алгоритма Кнута X использоваться для решения этого CSP ? В этой игре первый и последний номер всегда находятся на доске, и я верю, что у каждой хорошо сформулированной проблемы есть только одно решение.

Answer 1

Да.

Предположим, мы хотим решить эту проблему:

+---+   +---+
|   |   | 6 |
+---+---+---+
|   |   |
+---+---+
| 1 |   |
+---+---+

Сначала назовем пустые ячейки буквами a, b, c, d:

+---+   +---+
| d |   | 6 |
+---+---+---+
| b | c |
+---+---+
| 1 | a |
+---+---+

Нам необходимо выразить 3 вида ограничений для каждой строки решения алгоритма X :

• Используется номер (чтобы один и тот же номер не использовался дважды)
• Используется ячейка (чтобы одна и та же ячейка не использовалась дважды)
• Следующая ячейка ограничена (поэтому следующую ячейку можно выбрать только среди соседних). Последнее ограничение не требует точного покрытия, поэтому его следует использовать только как вторичные столбцы в терминологии DLX .

Матрица полученной проблемы имеет вид:

1 2 3 4 5 6 a b c d   2a 2b 2c 2d     3a 3b 3c 3d     4a 4b 4c 4d     5a 5b 5c 5d
1                              1
  1         1         1               1        1
  1           1          1               1
  1             1           1               1
  1               1            1      1        1
    1       1                         1               1        1
    1         1                          1               1
    1           1                           1               1
    1             1                            1      1        1
      1     1                                         1               1        1
      1       1                                          1               1
      1         1                                           1               1
      1           1                                            1      1        1
        1   1                                                         1
        1     1                                                          1
        1 1     1                                                           1
        1         1                                                            1

Где, например, вторая строка (без подсчета строки заголовка) может читаться как: эта строка устанавливает число 2 (первая 1) в ячейке a (вторая 1 ). Он также ограничен световым ограничением 2a . И это также ограничивает 3 не быть на 3a и 3d , потому что они не смежны с ячейкой a .

Все строки читаются таким образом, кроме:

• Первая строка, в которой указываются только ограничения на число 2 .
• 5 строк (4 последних), которые также включают ограничение на смежность с 6 .

Реализация оставлена ​​в качестве упражнения для читателя ...

Answer 2

номер

Решатель ограничений, безусловно, может решить эту проблему, но вряд ли это будет самый быстрый способ сделать это. На первый взгляд кажется, что решателю будет трудно сказать, что «путь не может пересекать себя», что является полезной подсказкой.