Ограничения Пролога -> Решаем головоломку
Ребята, я изучаю ограничения с помощью пролога и пытаюсь реализовать небольшую головоломку, используя эти новые знания.
Цель головоломки проста: у меня есть квадратная сетка с несколькими числами сверху / снизу каждого столбца и справа / слева от каждого ряда. Область значений изменяется от 0 до Gridsize -1, что означает, что сетка 7x7 может иметь числа от 0 до 6. Ограничения следующие:
- Каждое число может появляться только один раз в каждой строке и один раз в каждом столбце
- Число сверху / справа является суммой первой и последней цифр в столбце / строке соответственно
- Число внизу / слева является суммой цифр Second и SecondLast в столбце / строке соответственно
- Нули не считаются цифрами, они присутствуют только в программе для представления пробелов
Для примера:
TopConstraint = [7, 6, 4, 7, 3]
RightConstraint = [5, 5, 5, 5, 5]
BottomConstraint = [3, 4, 6, 3, 7]
LeftConstraint = [5, 5, 5, 5, 5]
Эти ограничения также могут иметь значение 0, что делает программу простым игнорированием (сумма может быть любым числом, если она соответствует другим ограничениям).
Одним из решений вышеупомянутых списков будет матрица:
3 | 4 | 1 | | 2
1 | 3 | 2 | 4 |
2 | | 4 | 1 | 3
| 1 | 3 | 2 | 4
4 | 2 | | 3 | 1
Теперь проблема в том, что мои ограничения почему-то не применяются, и программа не дает мне решения.
После установки правильного домена и размещения всех ячеек столбцов / строк по-разному (без каких-либо других ограничений это дает мне ожидаемое решение), у меня есть этот код для применения к каждой ячейке, сумма ограничений:
put_restrictions(Sol, Gridsize, SumT, SumR, SumB, SumL):-
put_restrictions_row(Sol, Gridsize, SumR, SumL, 1),
put_restrictions_col(Sol, Gridsize, SumT, SumB, 1).
Где Gridsize - это размер Grids для выполнения итераций, SumT, SumR, SumB, SumL, соответственно, приведенные выше списки ограничений, и 1 для запуска счетчика итераций.
Так что это предикаты, где моя проблема проживает
put_restrictions_col(_, Gridsize, _, _, X):- X > Gridsize, write('end put_restrictions_col'),nl.
put_restrictions_col(Grid, Gridsize, [SumTH|SumTT], [SumBH|SumBT], X):-
get_cell(Grid, FirstInCol, X, 1, Gridsize),
get_cell(Grid, LastInCol, X, Gridsize, Gridsize),
get_cell(Grid, SecondInCol, X, 2, Gridsize),
SecondLastIndex is Gridsize-1,
get_cell(Grid, SecondLastInCol, X, SecondLastIndex, Gridsize),
get_cell(Grid, ThirdInCol, X, 3, Gridsize),
ThirdLastIndex is Gridsize-2,
get_cell(Grid, ThirdLastInCol, X, ThirdLastIndex, Gridsize),
(SumTH #> 0) #=>
(
(((FirstInCol #> 0) #/\ (LastInCol #> 0)) #=> (SumTH #= FirstInCol + LastInCol))
#\/
((FirstInCol #= 0) #=> (SumTH #= SecondInCol + LastInCol))
#\/
((LastInCol #= 0) #=> (SumTH #= FirstInCol + SecondLastInCol))
),
(SumBH #> 0) #=>
(
(((SecondInCol #> 0) #/\ (SecondLastInCol #> 0)) #=> (SumBH #= SecondInCol + SecondLastInCol))
#\/
((SecondInCol #= 0) #=> (SumBH #= ThirdInCol + SecondLastInCol))
#\/
((SecondLastInCol #= 0) #=> (SumBH #= SecondInCol + ThirdLastInCol))
),
X1 is X+1,
put_restrictions_col(Grid, Gridsize, SumTT, SumBT, X1).
put_restrictions_row([], _, _,_,_):- write('end put_restrictions_row'),nl.
put_restrictions_row([H|T], Gridsize, [SumRH|SumRT],[SumLH|SumLT], N):-
element(1, H, FirstInRow),
element(Gridsize, H, LastInRow),
element(2, H, SecondInRow),
SecondLastIndex is Gridsize -1,
element(SecondLastIndex, H, SecondLastInRow),
element(3, H, ThirdInRow),
ThirdLastIndex is Gridsize -2,
element(ThirdLastIndex, H, ThirdLastInRow),
(SumRH #> 0) #=>
(
(((FirstInRow #> 0) #/\ (LastInRow #> 0)) #/\ (FirstInRow + LastInRow #= SumRH))
#\/
((FirstInRow #= 0) #/\ (SecondInRow + LastInRow #= SumRH))
#\/
((LastInRow #= 0) #/\ (FirstInRow + SecondLastInRow #= SumRH))
),
(SumLH #> 0) #=>
(
(((SecondInRow #> 0) #/\ (SecondLastInRow #> 0)) #/\ (SumLH #= SecondInRow + SecondLastInRow))
#\/
((SecondInRow #= 0) #/\ (SumLH #= ThirdInRow + SecondLastInRow))
#\/
((SecondLastInRow #= 0) #/\ (SumLH #= SecondInRow + ThirdLastInRow))
),
N1 is N+1,
put_restrictions_row(T, Gridsize, SumRT, SumLT, N1).
Я думаю, что код довольно понятен, если нет, то, что я пытаюсь сделать:
Если есть ограничение на правой стороне:
- Если первая и последняя ячейки строки не равны 0, то их сумма равна ограничению
- Если 1-я ячейка в строке равна 0, то сумма 2-й ячейки строки и последнего = с ограничением -> делает левое ограничение суммой 3-й ячейки слева и второй области И так далее.,
Я не получаю никакого решения по этой проблеме. Что я делаю неправильно, связывая ограничения?
Любая помощь приветствуется. Заранее благодарен за помощь прологу здесь:P
1 ответ
Я пытался решить, с более простым кодом...
restrictions :-
T = [7, 6, 4, 7, 3], % TopRestriction
R = [5, 5, 5, 5, 5], % RightRestriction
B = [3, 4, 6, 3, 7], % BottomRestriction
L = [5, 5, 5, 5, 5], % LeftRestriction
restrictions(T, R, B, L, Sol),
maplist(writeln, Sol).
restrictions(T, R, B, L, Rows) :-
% check all restrictions are properly sized
maplist(length_(N), [T, R, B, L]),
% solution is a square
length_(N, Rows),
maplist(length_(N), Rows),
transpose(Rows, Cols),
% main constraints
append(Rows, Vs),
N1 is N-1,
Vs ins 0..N1,
maplist(all_different, Rows),
%maplist(all_different, Cols),
% apply restrictions
maplist(restriction, Rows, L, R),
maplist(restriction, Cols, T, B),
% if constraints are not enough strong for an unique solution
label(Vs).
restriction(Tile, S1, S2) :-
append([A,B], R, Tile),
append(_, [C,D], R),
S1 #= 0 #\/ A #= 0 #\/ D #= 0 #\/ S1 #= A + D,
S2 #= 0 #\/ B #= 0 #\/ C #= 0 #\/ S2 #= B + C.
length_(N, L) :- length(L, N).
Обратите внимание на второе all_different ограничение закомментировано, так как, когда я публикую его, решение не будет найдено. Снятие ограничений (то есть "ослабление" решений) - это единственный "настоящий" инструмент отладки, который я смог найти до сих пор самостоятельно.
Образец решения:
?- restrictions.
[3,0,1,4,2]
[1,0,2,3,4]
[0,1,2,4,3]
[2,1,4,0,3]
[4,2,0,3,1]
true ;
[3,0,1,4,2]
[1,0,2,3,4]
[0,1,2,4,3]
[2,1,4,0,3]
[4,2,3,0,1]
...