% 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).