Prolog求解Sudoku

1、求解源码如下

:- use_module(library(clpfd)).

%求解函数
sudoku(Rows) :-
        length(Rows, 9),                                         %输入为9行
        maplist(length_(9), Rows),                               %每行长度必须为9
        append(Rows, Vs), Vs ins 1..9,                           %所有行拼接为一个List,数值都必须在1到9之间
        maplist(all_distinct, Rows),                             %每行没有重复数据
        transpose(Rows, Columns), maplist(all_distinct, Columns),%矩阵转置,每列没有重复数据
        Rows = [R1,R2,R3,R4,R5,R6,R7,R8,R9],                     %输入拆分为9行
        blocks(R1,R2,R3), blocks(R4,R5,R6), blocks(R7,R8,R9).    %按每3行进行处理

%为了适应maplist函数,调整参数顺序
length_(L, Ls) :- length(Ls, L).

%对于每3行,每次从各行抽取前3个值,恰好为1个3×3的矩阵,共抽取3个矩阵
%对于矩阵,拼接为一个List,并要求没有重复数据
blocks([], [], []).
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-
        all_distinct([A,B,C,D,E,F,G,H,I]),
        blocks(Bs1, Bs2, Bs3).

%这个是输入函数,就不需要命令行输入了
%第1个是一个sudoku问题
problem(1, [[_,_,_,_,_,_,_,_,_],
            [_,_,_,_,_,3,_,8,5],
            [_,_,1,_,2,_,_,_,_],
            [_,_,_,5,_,7,_,_,_],
            [_,_,4,_,_,_,1,_,_],
            [_,9,_,_,_,_,_,_,_],
            [5,_,_,_,_,_,_,7,3],
            [_,_,2,_,1,_,_,_,_],
            [_,_,_,_,4,_,_,_,9]]).
            
%第2个是一个多解的sudoku问题           
problem(2, [[_,9,1,_,4,7,_,_,_],
            [7,_,_,_,1,_,_,_,_],
            [_,_,_,6,5,_,_,_,_],
            [9,_,_,4,_,6,_,_,7],
            [_,_,_,7,3,5,_,_,6],
            [_,_,7,9,8,1,_,_,_],
            [1,_,6,5,7,8,9,_,4],
            [_,_,9,1,6,_,8,_,_],
            [_,_,_,3,9,4,_,_,1]]).
            
%第3个是通过2得到的唯一解sudoku问题            
problem(3, [[8,9,1,_,4,7,6,_,_],
            [7,_,_,_,1,_,_,_,_],
            [2,_,_,6,5,_,_,_,_],
            [9,_,_,4,_,6,_,_,7],
            [_,_,_,7,3,5,_,_,6],
            [_,_,7,9,8,1,_,_,_],
            [1,_,6,5,7,8,9,_,4],
            [_,_,9,1,6,_,8,_,_],
            [_,_,_,3,9,4,_,_,1]]).

2、尝试一下

1 ?- problem(1, Rows), sudoku(Rows), maplist(writeln, Rows).
[9,8,7,6,5,4,3,2,1]
[2,4,6,1,7,3,9,8,5]
[3,5,1,9,2,8,7,4,6]
[1,2,8,5,3,7,6,9,4]
[6,3,4,8,9,2,1,5,7]
[7,9,5,4,6,1,8,3,2]
[5,1,9,2,8,6,4,7,3]
[4,7,2,3,1,9,5,6,8]
[8,6,3,7,4,5,2,1,9]
Rows = [[9, 8, 7, 6, 5, 4, 3, 2|...], [2, 4, 6, 1, 7, 3, 9|...], [3, 5, 1, 9, 2, 8|...], [1, 2, 8, 5, 3|...], [6, 3, 4, 8|...], [7, 9, 5|...], [5, 1|...], [4|...], [...|...]].

2 ?- problem(2, Rows), sudoku(Rows), maplist(writeln, Rows).
[_G296,9,1,_G320,4,7,_G344,_G368,_G392]
[7,_G416,_G440,_G464,1,_G488,_G512,_G536,_G560]
[_G584,_G608,_G632,6,5,_G656,7,1,_G728]
[9,_G752,_G776,4,2,6,_G824,8,7]
[_G872,_G896,_G920,7,3,5,_G944,9,6]
[_G992,_G1016,7,9,8,1,_G1040,_G1064,_G1088]
[1,_G1112,6,5,7,8,9,_G1136,4]
[_G1160,_G1184,9,1,6,2,8,_G1232,_G1256]
[_G1280,_G1304,_G1328,3,9,4,_G1352,_G1376,1]
Rows = [[_G24117, 9, 1, _G24126, 4, 7, _G24135, _G24138|...], [7, _G24150, _G24153, _G24156, 1, _G24162, _G24165|...], [_G24177, _G24180, _G24183, 6, 5, _G24192|...], [9, _G24210, _G24213, 4, 2|...], [_G24237, _G24240, _G24243, 7|...], [_G24267, _G24270, 7|...], [1, _G24300|...], [_G24327|...], [...|...]],
_G24117 in 2..3\/5..6\/8,
all_distinct([_G24117, 9, 1, 7, _G24150, _G24153, _G24177, _G24180|...]),
all_distinct([_G24117, 7, _G24177, 9, _G24237, _G24267, 1, _G24327|...]),
all_distinct([_G24117, 9, 1, _G24126, 4, 7, _G24135, _G24138|...]),
_G24150 in 2..6\/8,
all_distinct([9, _G24150, _G24180, _G24210, _G24240, _G24270, _G24300, _G24330|...]),
all_distinct([7, _G24150, _G24153, _G24156, 1, _G24162, _G24165, _G24168|...]),
_G24153 in 2..5\/8,
all_distinct([1, _G24153, _G24183, _G24213, _G24243, 7, 6, 9|...]),
_G24177 in 2..4\/8,
all_distinct([_G24177, _G24180, _G24183, 6, 5, _G24192, 7, 1|...]),
_G24180 in 2..4\/8,
_G24183 in 2..4\/8,
_G24213 in 3\/5,
all_distinct([9, _G24210, _G24213, _G24237, _G24240, _G24243, _G24267, _G24270|...]),
all_distinct([9, _G24210, _G24213, 4, 2, 6, _G24225, 8|...]),
_G24237 in 2\/4\/8,
all_distinct([_G24237, _G24240, _G24243, 7, 3, 5, _G24255, 9|...]),
_G24240 in 1..2\/4\/8,
_G24243 in 2\/4\/8,
_G24267 in 2..6,
all_distinct([_G24267, _G24270, 7, 9, 8, 1, _G24285, _G24288|...]),
_G24270 in 2..6,
_G24210 in 1\/3\/5,
_G24300 in 2..3,
all_distinct([1, _G24300, 6, _G24327, _G24330, 9, _G24357, _G24360|...]),
all_distinct([1, _G24300, 6, 5, 7, 8, 9, _G24318|...]),
_G24327 in 3..5,
all_distinct([_G24327, _G24330, 9, 1, 6, 2, 8, _G24348|...]),
_G24330 in 3..5\/7,
_G24357 in 2\/5\/8,
all_distinct([_G24357, _G24360, _G24363, 3, 9, 4, _G24375, _G24378|...]),
_G24360 in 2\/5\/7..8,
_G24363 in 2\/5\/8,
_G24375 in 2\/5..6,
all_distinct([9, _G24318, 4, 8, _G24348, _G24351, _G24375, _G24378|...]),
all_distinct([_G24135, _G24165, 7, _G24225, _G24255, _G24285, 9, 8|...]),
_G24378 in 2\/5..7,
all_distinct([_G24138, _G24168, 1, 8, 9, _G24288, _G24318, _G24348|...]),
_G24351 in 3\/5,
all_distinct([_G24141, _G24171, _G24201, 7, 6, _G24291, 4, _G24351|...]),
_G24348 in 3\/5\/7,
_G24318 in 2..3,
_G24288 in 2..5,
all_distinct([_G24225, 8, 7, _G24255, 9, 6, _G24285, _G24288|...]),
_G24291 in 2..3\/5,
_G24285 in 2..5,
_G24255 in 1..2\/4,
_G24225 in 1\/3\/5,
_G24165 in 2..6,
all_distinct([_G24135, _G24138, _G24141, _G24165, _G24168, _G24171, 7, 1|...]),
_G24168 in 2..6,
_G24171 in 2..3\/5\/8..9,
_G24201 in 2..3\/8..9,
_G24141 in 2..3\/5\/8,
_G24138 in 2..3\/5..6,
_G24135 in 2..3\/5..6,
_G24126 in 2\/8,
all_distinct([_G24126, 4, 7, _G24156, 1, _G24162, 6, 5|...]),
all_distinct([_G24126, _G24156, 6, 4, 7, 9, 5, 1|...]),
_G24156 in 2\/8,
_G24162 in 3\/9,
all_distinct([7, _G24162, _G24192, 6, 5, 1, 8, 2|...]),
_G24192 in 3\/9.

%根据2的提示,填写部分不确定的值后,可以得到问题3,根据选择不同,答案也不同
3 ?- problem(3, Rows), sudoku(Rows), maplist(writeln, Rows).
[8,9,1,2,4,7,6,5,3]
[7,6,5,8,1,3,4,2,9]
[2,3,4,6,5,9,7,1,8]
[9,1,3,4,2,6,5,8,7]
[4,8,2,7,3,5,1,9,6]
[6,5,7,9,8,1,3,4,2]
[1,2,6,5,7,8,9,3,4]
[3,4,9,1,6,2,8,7,5]
[5,7,8,3,9,4,2,6,1]
Rows = [[8, 9, 1, 2, 4, 7, 6, 5|...], [7, 6, 5, 8, 1, 3, 4|...], [2, 3, 4, 6, 5, 9|...], [9, 1, 3, 4, 2|...], [4, 8, 2, 7|...], [6, 5, 7|...], [1, 2|...], [3|...], [...|...]].

Comments are closed.