В следующей головоломке мы пытаемся заполнить сетку синими и белыми квадратами таким образом, чтобы:
- 3 в ряд (или столбец) одного цвета не допускаются.
- В каждой строке и столбце равное количество синих и белых квадратов.
Если мы теперь представим белый с 0 и синий с 1, мы получим:
0 _ _ _ 1 _
_ 0 _ _ _ _
_ _ _ _ _ 0
1 _ _ 0 _ _
_ _ 1 1 _ _
_ 0 _ _ 1 _
И мы можем довольно быстро убедиться, что
0 1 0 0 1 1
0 0 1 1 0 1
1 1 0 1 0 0
1 1 0 0 1 0
0 0 1 1 0 1
1 0 1 0 1 0
является решением для этого примера.
В качестве ограничений я написал следующее:
constraints(Board,N) :-
N2 is N // 2,
( for(I,1,N), param(Board,N2,N)
do
Row is Board[I,1..N],
Col is Board[1..N,I],
ic_global:sequence_total(N2,N2,1,2,3,Row),
ic_global:sequence_total(N2,N2,1,2,3,Col)
).
sequence_total/6 гарантирует, что значение 1 должно встречаться ровно N2 раз (половина раз от N) в строке/столбце и что каждая последовательность в указанной строке/столбце из 3 элементов должна содержать от 1 до 2 раз больше значения 1 (так что никакие 3 квадрата со значением 1 не могут появляться рядом друг с другом ).
Я получаю следующие результаты для экземпляра головоломки 18x18 (*):
Solved in 147 backtracks
Yes (10.39s cpu, solution 1)
Похоже, что ограничения делают свою работу очень хорошо, прежде чем будет выполнен какой-либо поиск, поскольку необходимы «всего» 147 возвратов. Однако время работы кажется мне очень долгим, особенно по сравнению с количеством возвратов. Я предполагаю, что это связано со всей проверкой последовательности, которая должна произойти? Тот факт, что изменение любого из методов выбора/выбора в search/6 практически не влияет на время работы, что подтверждает это.
Если да, то существуют ли какие-либо другие, более эффективные способы ограничить последовательности в списке/массиве, чтобы не иметь N одинаковых элементов рядом друг с другом и улучшить время выполнения?
ИЗМЕНИТЬ
После использования декомпозированной версии, предоставленной @jschimpf ниже, получены следующие результаты:
Solved in 310 backtracks
Yes (0.22s cpu, solution 1)
Новые ограничения не такие сильные, как sequence/6, нам нужно немного больше возвратов, но наше время выполнения сократилось с 10,39 до 0,22 секунды, так что общий результат очень желателен.
Пример данных:
Головоломка, используемая для этого вопроса (решает без возвратов)
задача(р(6,1),[(1,1,0),(1,5,1),(2,2,0),(3,6,0),(4,1,1), (4,4,0),(5,3,1),(5,4,1),(6,2,0),(6,5,1)]).
Головоломка (*), по которой я выложил свои результаты:
задача(р(18,1),[(1,3,0),(1,9,0),(1,10,0),(1,12,0),(1,14,0), (1,18,1),(2,4,0),(2,7,1),(2,8,1),(3,2,1),(3,6,0),(3 ,16,0),(3,17,0),(4,2,1),(4,4,1),(4,10,1),(4,13,1),(4,18 ,1),(5,8,1),(5,10,1),(5,15,0),(5,16,1),(6,12,1),(7,3,0 ),(7,4,0),(7,6,1),(7,9,0),(7,12,1),(7,17,0),(8,1,1), (8,4,0),(8,8,1),(8,15,1),(8,16,1),(9,7,0),(9,10,0),(9 ,14,0),(10,2,1),(10,4,1),(10,6,1),(10,13,1),(11,7,0),(11,10 ,1),(12,1,1),(12,4,1),(12,7,1),(12,15,1),(12,16,1),(13,1,1) ),(13,6,0),(13,8,1),(13,10,0),(13,16,1),(14,5,1),(14,10,0), (14,13,1),(15,1,1),(15,3,1),(15,12,0),(15,13,1),(15,15,0),(16 ,2,1),(16,4,0),(16,12,0),(16,18,0),(17,9,0),(17,15,0),(17,18 ,0),(18,2,1),(18,8,1),(18,11,1),(18,15,1),(18,16,1)]).
','(1,','(1,0))
, т. е. вложенные И, также называемые И-списками. Например, более чистое представление:x_y_v(1, 1, 0)
. - person mat   schedule 24.03.2016(1, 2, 3) = (X, Y)
будет оцениваться как true, я вижу, как это может привести к неожиданным результатам. Спасибо за подсказку! - person SND   schedule 24.03.2016(-)/2
для представления пар, а не','/2
или(.)/2
! Это соглашение используется во многих библиотечных предикатах, обрабатывающих пары, поскольку оно сочетает в себе краткий синтаксис и эффективное хранение — в большинстве систем Prologfoo-bar
занимает (немного) меньше памяти, чем[foo,bar]
. Для троек следуйте совету @mat! - person repeat   schedule 25.03.2016