% Usage: solve(boardname). % % For example: % % | ?- solve(smh20050603). % % +-------+-------+-------+ % | 8 7 6 | 4 9 5 | 3 2 1 | % | 1 3 2 | 8 7 6 | 5 9 4 | % | 5 9 4 | 2 3 1 | 8 6 7 | % +-------+-------+-------+ % | 4 5 3 | 1 6 8 | 2 7 9 | % | 2 6 9 | 3 4 7 | 1 5 8 | % | 7 1 8 | 5 2 9 | 4 3 6 | % +-------+-------+-------+ % | 3 4 7 | 6 1 2 | 9 8 5 | % | 6 8 1 | 9 5 3 | 7 4 2 | % | 9 2 5 | 7 8 4 | 6 1 3 | % +-------+-------+-------+ % % (3 ms) yes % % solve(any) will run through all possible solutions. sudoku( smh20050603, [ [ 8, _, _, _, _, _, _, _, 1], [ _, 3, _, 8, 7, 6, _, 9, _], [ _, 9, _, _, _, _, _, 6, _], [ _, _, 3, 1, _, 8, 2, _, _], [ _, 6, _, _, _, _, _, 5, _], [ _, _, 8, 5, _, 9, 4, _, _], [ _, 4, _, _, _, _, _, 8, _], [ _, 8, _, 9, 5, 3, _, 4, _], [ 9, _, _, _, _, _, _, _, 3] ] ). sudoku( any, [ [ _, _, _, _, _, _, _, _, _], [ _, _, _, _, _, _, _, _, _], [ _, _, _, _, _, _, _, _, _], [ _, _, _, _, _, _, _, _, _], [ _, _, _, _, _, _, _, _, _], [ _, _, _, _, _, _, _, _, _], [ _, _, _, _, _, _, _, _, _], [ _, _, _, _, _, _, _, _, _], [ _, _, _, _, _, _, _, _, _] ] ). split([], [], []). split([ [ TopLeft | TopRight ] | Rest ], [ TopLeft | RestLeft ], [ TopRight | RestRight ]) :- split(Rest, RestLeft, RestRight), !. transpose([], []). transpose([ [ TopLeft | TopRight ] | Rest ], [ [ TopLeft | LeftColumn ] | TransposedRest ]) :- split(Rest, LeftColumn, Sub), transpose(Sub, TransposedSub), split(TransposedRest, TopRight, TransposedSub), !. twiddle([], []). twiddle( [ [ A1, A2, A3, A4, A5, A6, A7, A8, A9 ], [ B1, B2, B3, B4, B5, B6, B7, B8, B9 ], [ C1, C2, C3, C4, C5, C6, C7, C8, C9 ] | Rest ], [ [ A1, A2, A3, B1, B2, B3, C1, C2, C3 ], [ A4, A5, A6, B4, B5, B6, C4, C5, C6 ], [ A7, A8, A9, B7, B8, B9, C7, C8, C9 ] | TwiddledRest ] ) :- twiddle(Rest, TwiddledRest), !. domain_all([]). domain_all([ Row | Rest ]) :- domain_all(Rest), fd_domain(Row, 1, 9), !. valid_block(A) :- fd_all_different(A), !. all_valid_blocks([]). all_valid_blocks([ Block | Rest ]) :- valid_block(Block), all_valid_blocks(Rest), !. label_all([]). label_all([ Row | Rest ]) :- fd_labeling(Row), label_all(Rest). print_board([]) :- format("+-------+-------+-------+\n", []). print_board([ A, B, C | Rest ]) :- format("+-------+-------+-------+\n", []), format("| ~p ~p ~p | ~p ~p ~p | ~p ~p ~p |\n", A), format("| ~p ~p ~p | ~p ~p ~p | ~p ~p ~p |\n", B), format("| ~p ~p ~p | ~p ~p ~p | ~p ~p ~p |\n", C), print_board(Rest), !. solution(Board) :- domain_all(Board), transpose(Board, T1), twiddle(Board, T2), all_valid_blocks(Board), all_valid_blocks(T1), all_valid_blocks(T2), label_all(Board). solve(Name) :- sudoku(Name, Board), solution(Board), format("\n", []), print_board(Board).