Prolog解析FEN串递归列表回溯异常多结果问题排查

问题相关原始代码 #

rank(1).
rank(2).
rank(3).
rank(4).
rank(5).
rank(6).
rank(7).
rank(8).


fold_rank(Rank, [], [], _).
fold_rank(Rank, [_Rank|Rest], Files, SS) :- 
  rank(_Rank),
  length(RemoveFiles, _Rank),
  append(RemoveFiles, _Files, Files),
  fold_rank(Rank, Rest, _Files, SS).


fold_rank(Rank, [Role|Rest], [File|FRest], [Role-File|SS]) :-
  fold_rank(Rank, Rest, FRest, SS).

需求背景 #

需要解析国际象棋FEN字符串的单行列片段，规则如下：

• 输入可以是全棋子字符，例如kqpnbrqk
• 也可以用数字表示连续跳过的空位，例如8、1qpnbrqk、4br1k、kqn5，数字代表的空位数量加棋子字符数总长度固定为8
• 最终要把棋子字符和a~h的列标识一一配对，数字对应的空位直接跳过不配对

问题表现 #

• 处理无数字输入时逻辑正常：

?- fold_rank(8, [l,x,y,z], [a,b,d,c], Ls).
Ls = [l-a, x-b, y-d, z-c|_] ;
false.

• 处理带数字的输入时返回大量非预期结果：

?- fold_rank(8, [1,l,l,1], [a,b,d,c], Ls).
Ls = [l-b, l-d|_] ;
Ls = [l-b, l-d, 1-c|_] ;
Ls = [1-a, l-b, l-d|_] ;
Ls = [1-a, l-b, l-d, 1-c|_] ;
false.

问题根源 #

出现多组非预期结果是两个逻辑缺陷共同导致的：

1. 两个递归子句的匹配范围重叠。处理棋子的子句匹配模式为[Role|Rest]，可以匹配任意非空列表，包括首元素为数字的情况。也就是说当输入元素是数字时，Prolog回溯时既可以走「跳过空位」的逻辑，也可以走「棋子配对」的逻辑，把数字当成普通棋子和列绑定，因此会出现1-a、1-c这类错误结果。
2. 空位匹配逻辑没有约束输入值。处理空位的子句中，仅用rank(_Rank)枚举1_{8的合法空位数，没有判断当前列表首元素是否真的等于枚举到的数值，导致跳过的列数可以是任意1}8的值，和输入数字无关，生成大量错误配对。
   此外基准子句fold_rank(Rank, [], [], _).要求剩余棋子、剩余列同时为空才终止，但逻辑中没有强制总长度校验，会出现列表未处理完就截断、留下未绑定尾变量的问题。

修复方案 #

重写谓词逻辑，严格区分数字和棋子类型，匹配数字时强制和跳过列数相等，最终自动校验总长度：

rank(1).
rank(2).
rank(3).
rank(4).
rank(5).
rank(6).
rank(7).
rank(8).

% 基准情况：所有输入处理完成，无剩余列
fold_rank([], [], []).

% 处理数字空位：当前元素为1-8的合法数字，跳过对应数量的列后处理剩余内容
fold_rank([N|RestRoles], Files, SS) :-
  rank(N),
  length(RemoveFiles, N),
  append(RemoveFiles, RestFiles, Files),
  fold_rank(RestRoles, RestFiles, SS).

% 处理棋子：当前元素非数字，和当前列绑定后处理剩余内容
fold_rank([Role|RestRoles], [File|RestFiles], [Role-File|SS]) :-
  \+ rank(Role),
  fold_rank(RestRoles, RestFiles, SS).

修复后测试带数字的输入将仅返回正确结果：

?- fold_rank([1,l,l,1], [a,b,c,d], Ls).
Ls = [l-b, l-c] ;
false.

处理完整8列FEN行时，直接传入初始列列表[a,b,c,d,e,f,g,h]即可，逻辑会自动校验数字+棋子的总长度是否为8，不符合规则的输入会直接返回false。

内容的提问来源于stack exchange，提问作者eguneys