Логическая головоломка "3 в ряд": оптимизация ограничений последовательности в списках / массивах

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

  • 3-в-ряд (или столбец) одного цвета не допускается.
  • Каждая строка и столбец имеют одинаковое количество синих и белых квадратов.

example_puzzle

Если мы теперь представим белый с 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 ответ

Решение

Оказывается, что в этом случае разложенная вручную версия ограничения последовательности является гораздо более эффективной. Использовать например

sequence_1_2([X1,X2,X3|Xs]) :- !,
    S #:: 1..2,
    X1+X2+X3 #= S,
    sequence_1_2([X2,X3|Xs]).
sequence_1_2(_).

который ограничивает сумму любой 3-элементной подпоследовательности 1 или 2, и заменяет ограничения sequence_total/6 на

    ...,
    sum(Row) #= N2,
    sequence_1_2(Row),

Это сокращает время решения до 0,2 секунды.

Источник
Другие вопросы по тегам