Prolog填字游戏程序：谓词无法返回列表及无限生成空列表问题

初始问题描述 #

我正在开发一款求解方形填字游戏的Prolog程序，程序通过dimension(X)和black(X,Y)谓词定义游戏参数：

• dimension(X)：表示填字游戏网格的尺寸
• black(X,Y)：标记网格中黑格的坐标

需求是生成所有可填入单词的位置列表——即所有连续的横向/纵向白格段（不能被黑格中断），先从横向位置入手：

1. 收集当前行的连续白格，直到遇到黑格或行尾
2. 移除已处理的白格和黑格，重复上述操作

目前打印的结果符合预期，但主谓词始终无法获取完整列表，输出为no。

初始代码 #

dimension(5).
black(1,3).
black(2,3).
black(3,2).
black(4,3).
black(5,1).
black(5,5).
words([adam,al,as,do,lis,ma,oker,ore,pirus,po,so,ur]).

crossword(L):-
    squares(Squares),
    generate_x_variables(Squares, 1, L).

squares(List):-
    dimension(Dimension),
    findall(X-Y, (between(1, Dimension, X), between(1, Dimension, Y)), List).


generate_x_variables([], _, []).
generate_x_variables(Squares, Row, [Variable|Variables]):-
    take_while(is_white_square, Squares, Row, Variable),
    write("Variable:    "), write(Variable), nl,
    drop_while(is_white_square, Squares, Row, RemainingSquares),
    drop_while(is_black_square, RemainingSquares, Row, UpdatedRemainingSquares),
    nth0(0, UpdatedRemainingSquares, X-Y),
    (X \= Row -> TempRow is Row + 1 ; TempRow is Row),
    generate_x_variables(UpdatedRemainingSquares, TempRow, Variables)


take_while(_, [], Row, []).
take_while(Predicate, [X-Y|Xs], Row, [X-Y|Taken]):-
    call(Predicate, X-Y, Row),
    take_while(Predicate, Xs, Row, Taken).
take_while(Predicate, [X-Y|_], Row, []) :-
    \+ call(Predicate, X-Y, Row).
    
is_white_square(X-Y, Row):-
    \+ black(X, Y),
    X=:=Row.

is_black_square(X-Y, Row):-
    black(X, Y),
    X=:=Row.

drop_while(_, [], Row, []).
drop_while(Predicate, [X-Y|Xs], Row, Remaining):-
    call(Predicate, X-Y, Row),
    drop_while(Predicate, Xs, Row, Remaining).
drop_while(Predicate, [X-Y|Xs], Row, [X-Y|Xs]) :-
    \+ call(Predicate, X-Y, Row).
    
nth0(0, [X|_], X).
nth0(N, [_|Xs], Element) :-
    N > 0,
    N1 is N - 1,
    nth0(N1, Xs, Element).

打印输出 #

Variable:    [1 - 1, 1 - 2]
Variable:    [1 - 4, 1 - 5]
Variable:    [2 - 1, 2 - 2]
Variable:    [2 - 4, 2 - 5]
Variable:    [3 - 1]
Variable:    [3 - 3, 3 - 4, 3 - 5]
Variable:    [4 - 1, 4 - 2]
Variable:    [4 - 4, 4 - 5]
Variable:    []
Variable:    [5 - 2, 5 - 3, 5 - 4]

修改后新问题 #

感谢@Scott Hunter修复了初始问题（原问题是nth0谓词未处理输入列表为空的情况），现在能打印出所需列表，但会无限循环点击"more"，不断向结果中添加空列表。

修改后的代码片段 #

generate_x_variables([], Row, _):-
    dimension(Dimension),
    Row > Dimension.
generate_x_variables(Squares, Row, [Variable|Variables]):-
    write("Squares list    "), write(Squares), nl,
    take_while(is_white_square, Squares, Row, Variable),
    write("Variable taken:    "), write(Variable), nl,
    drop_while(is_white_square, Squares, Row, RemainingSquares),
    write("After removing whites:    "), write(RemainingSquares), nl,
    drop_while(is_black_square, RemainingSquares, Row, UpdatedRemainingSquares),
    write("After removing blacks:    "), write(UpdatedRemainingSquares), nl, 
    nth0(0, UpdatedRemainingSquares, X-Y),
    write("First element of rest:   "), write(X-Y), nl,
    (X \= Row -> TempRow is Row + 1 ; TempRow is Row),
    write("Current row:    "), write(TempRow),  nl,
    generate_x_variables(UpdatedRemainingSquares, TempRow, Variables).

问题核心 #

1. 初始问题：主谓词crossword(L)为何无法获取打印出的变量列表，输出no？
2. 修改后问题：为何会无限生成空列表，导致"more"无限循环？

解决方案 #

初始问题根源与修复 #

原代码存在两个致命问题：

1. nth0未处理空列表：当UpdatedRemainingSquares为空时，nth0(0, UpdatedRemainingSquares, X-Y)会直接失败，导致整个谓词回溯返回no。
2. 终止条件不完整：原终止条件generate_x_variables([], _, [])未考虑行号是否超出网格尺寸，当处理完所有行后，即使列表为空，后续逻辑仍会尝试匹配递归子句，导致失败。

修改后无限循环的根源与修复 #

修改后的代码虽然添加了行号判断的终止条件，但递归子句没有处理当前行已无剩余格子但行号未超出尺寸的情况，同时允许空的白格段（Variable为空）加入结果，导致不断生成空列表，触发无限回溯。

修正后的核心代码

generate_x_variables([], Row, []):-
    dimension(Dimension),
    Row > Dimension.
generate_x_variables([], Row, L):-
    Row =< Dimension,
    NextRow is Row + 1,
    generate_x_variables([], NextRow, L).
generate_x_variables(Squares, Row, L):-
    take_while(is_white_square, Squares, Row, []),
    drop_while(is_white_square, Squares, Row, RemainingSquares),
    drop_while(is_black_square, RemainingSquares, Row, UpdatedRemainingSquares),
    (UpdatedRemainingSquares = [] ->
        NextRow is Row + 1;
        nth0(0, UpdatedRemainingSquares, X-Y),
        (X \= Row -> NextRow is Row + 1 ; NextRow = Row)
    ),
    generate_x_variables(UpdatedRemainingSquares, NextRow, L).
generate_x_variables(Squares, Row, [Variable|Variables]):-
    take_while(is_white_square, Squares, Row, Variable),
    Variable \= [],
    drop_while(is_white_square, Squares, Row, RemainingSquares),
    drop_while(is_black_square, RemainingSquares, Row, UpdatedRemainingSquares),
    (UpdatedRemainingSquares = [] ->
        NextRow is Row + 1;
        nth0(0, UpdatedRemainingSquares, X-Y),
        (X \= Row -> NextRow is Row + 1 ; NextRow = Row)
    ),
    generate_x_variables(UpdatedRemainingSquares, NextRow, Variables).

关键优化点

• 拆分递归逻辑：分别处理空白格段、非空白格段、列表为空但行号未结束的情况，避免无效回溯。
• 空列表前置判断：处理UpdatedRemainingSquares时先判断是否为空，避免调用nth0失败。
• 过滤空变量：仅当Variable非空时才加入结果列表，避免空列表污染输出。

内容的提问来源于stack exchange，提问作者Δημήτρης Μπακίρης