Question

Write Prolog code which can solve any given 9x9 Sudoku puzzle. Test your implementation with at least 2 querries and show the results in README. Writing README carries 1 point.

Answer 1

:- initialization(main).
 
 
solveNineNineSudoku(Rows) :-
    maplist(numbers_from_1_9, Rows)
  , different(Rows)
  , transposeSudoku(Rows,Cols), different(Cols)
  , blocks(Rows,Blocks) , different(Blocks)
  , maplist(fd_labeling, Rows)
  .
 
numbers_from_1_9(Rows) :- fd_domain(Rows,1,9).
different(Rows)  :- maplist(fd_all_different, Rows).
 
blocks(Rows,Blocks) :-
    maplist(split3,Rows,Xs), transposeSudoku(Xs,Ys)
  , concat(Ys,Zs), concat_map(split3,Zs,Blocks)
  . 
    split3([X,Y,Z|L],[[X,Y,Z]|R]) :- split3(L,R).
    split3([],[]).
 
 

concat_map(F,Xs,Ys) :- call(F,Xs,Zs), maplist(concat,Zs,Ys).
 
concat([],[]).
concat([X|Xs],Ys) :- append(X,Zs,Ys), concat(Xs,Zs).
 
transposeSudoku([],[]).
transposeSudoku([[X]|Col], [[X|Row]]) :- transposeSudoku(Col,[Row]).
transposeSudoku([[X|Row]], [[X]|Col]) :- transposeSudoku([Row],Col).
transposeSudoku([[X|Row]|Xs], [[X|Col]|Ys]) :-
    maplist(bind_head, Row, Ys, YX)
  , maplist(bind_head, Col, Xs, XY)
  , transposeSudoku(XY,YX)
  . 
    bind_head(H,[H|T],T).
    bind_head([],[],[]).
 
 

query([ [_,_,3,_,_,_,_,_,_]
     , [4,_,_,_,8,_,_,3,6]
     , [_,_,8,_,_,_,1,_,_]
     , [_,4,_,_,6,_,_,7,3]
     , [_,_,_,9,_,_,_,_,_]
     , [_,_,_,_,_,2,_,_,5]
     , [_,_,4,_,7,_,_,6,8]
     , [6,_,_,_,_,_,_,_,_]
     , [7,_,_,6,_,_,5,_,_]
     ]).

 
main :- query(T), solveNineNineSudoku(T), maplist(show,T), halt.
show(X) :- write(X), nl.

QUERY 1:

query([[_,_,_,_,_,_,_,_,_],
            [_,_,_,_,_,3,_,8,5],
            [_,_,1,_,2,_,_,_,_],
            [_,_,_,5,_,7,_,_,_],
            [_,_,4,_,_,_,1,_,_],
            [_,9,_,_,_,_,_,_,_],
            [5,_,_,_,_,_,_,7,3],
            [_,_,2,_,1,_,_,_,_],
            [_,_,_,_,4,_,_,_,9]]).

output:

[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]

QUERY 2:

query([ [_,_,3,_,_,_,_,_,_]
     , [4,_,_,_,8,_,_,3,6]
     , [_,_,8,_,_,_,1,_,_]
     , [_,4,_,_,6,_,_,7,3]
     , [_,_,_,9,_,_,_,_,_]
     , [_,_,_,_,_,2,_,_,5]
     , [_,_,4,_,7,_,_,6,8]
     , [6,_,_,_,_,_,_,_,_]
     , [7,_,_,6,_,_,5,_,_]
     ]).

output:

[1,2,3,4,5,6,7,8,9]
[4,5,7,1,8,9,2,3,6]
[9,6,8,3,2,7,1,5,4]
[2,4,9,5,6,1,8,7,3]
[5,7,6,9,3,8,4,1,2]
[8,3,1,7,4,2,6,9,5]
[3,1,4,2,7,5,9,6,8]
[6,9,5,8,1,4,3,2,7]
[7,8,2,6,9,3,5,4,1]