所以伙计们,我正在用 prolog 学习约束,并尝试使用这些新知识来实现一个小难题。
这个谜题的目标很简单:我有一个方形网格,每列的顶部/下方以及每行的右侧/左侧都有一些数字。值的域从 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是对其进行迭代的Gridsize,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,则它们的总和为 = 限制
- 如果该行的第一个单元格为 0,则该行的第二个单元格与限制的最后一个 = 的总和 -> 使左侧限制为左侧第三个单元格和倒数第二个单元格的总和等等。 .
我没有得到任何解决这个问题的办法。我在关联约束时做错了什么?
欢迎任何帮助。提前感谢您在这里帮助prologNoob:P