/* -*- Prolog -*- */

 /* 数独パズルを解くプログラム */

 /* 空いたマスに数を(他の条件と矛盾しないように)埋め、続いて他の空いた
    マスを同じように埋め…ということを、全てのマスが埋まるかあるいは
    条件が矛盾してマスが埋められなくなるまで行い、埋められなくなったら
    引き返して別な数を埋めてみる、というやり方で、数独パズルを解きます */

 /* 動かすにはこのファイルをconsultして、?- go. とします。
    SWISHの場合は、タブを開いてこのプログラムをカット&ペーストし、
    画面右下queryのところにgo.と入力してRunをクリックします */

 /* 問題の盤面を定義(問題を変更するには、ここを直接書き換える) */
board(
	row(
		col(1,4,_,2,_,_,7,_,_),
		col(7,_,_,5,_,_,9,_,_),
		col(_,_,_,_,_,9,_,8,4),
		col(_,_,_,_,3,_,_,_,_),
		col(_,_,8,_,_,_,6,_,_),
		col(2,_,_,8,_,_,_,_,7),
		col(_,_,_,_,6,_,1,_,_),
		col(_,_,2,_,_,_,_,_,_),
		col(5,_,_,1,_,_,_,9,_)
	)
).

 /* 2重の複合項を2次元配列とみなし、その要素にアクセス */
getElement(Array, X, Y, Elt) :-
	arg(Y, Array, Col), arg(X, Col, Elt).
	
 /* 問題を解く */
go :-
	board(Board), /* 盤面を得て */
	solve(Board), /* 解を探して */
	nl, output_solution(Board), fail.
	/* 改行して解を出力。失敗ループにより他の解も探す */
go. /* 失敗ループを用いるため、最後に無条件に成功させる */

 /* 与えられた盤面に対する解を探す */
solve(Board) :-
	check_and_rest(Board, 1, 1).

 /* 与えられた盤面Boardの座標(X, Y)以後の解を探す */
check_and_rest(Board, X, Y) :-
	getElement(Board, X, Y, Num), /* 盤面中の座標(X, Y)の要素にアクセスし*/
	generate_candidate(Num),  /* その要素に入る数(1〜9)の候補を生成し */
	\+ dup_col(Board, X, Y, Num), /* 横方向に重複がないか検査し */
	\+ dup_row(Board, X, Y, Num), /* 縦方向に重複がないか検査し */
	\+ dup_3x3(Board, X, Y, Num), /* 3×3のマス内に重複がないか検査し */
	rest(Board, X, Y). /* (X, Y)の次のマス以後の解を探す */
 /* 盤面内のある要素に入る数(1〜9)の候補を生成 */
generate_candidate(Num) :-
	nonvar(Num), !. /* 既に代入済みならそれ以外の解は生成しない */
generate_candidate(Num) :-
	between(1, 9, Num). /* 候補として1から9までの数を非決定的に生成 */
 /* 与えられた盤面Boardの座標(X, Y)の次のマス以後の解を探す */
rest(Board, X, Y) :- X < 9, !,
	X1 is X+1, /* (X, Y)の1つ右のマス(X1, Y)以降の解を探す */
	check_and_rest(Board, X1, Y).
rest(Board, 9, Y) :- Y < 9, !,
	Y1 is Y+1, /* (X, Y)の1つ下の段の左端(1, Y1)以降の解を探す */
	check_and_rest(Board, 1, Y1).
rest(_, 9, 9). /* もう最後のマスまで解を探し終わった */

 /* 座標(X, Y)の数が横方向に重複していることを検査 */
dup_col(Board, X, Y, Num) :-
	between(1, 9, X1), X1 \= X,
	getElement(Board, X1, Y, Num1), Num1 == Num.
 /* 座標(X, Y)の数が縦方向に重複していることを検査 */
dup_row(Board, X, Y, Num) :-
	between(1, 9, Y1), Y1 \= Y,
	getElement(Board, X, Y1, Num1), Num1 == Num.
 /* 座標(X, Y)の数が3×3のマス内で重複していることを検査 */
dup_3x3(Board, X, Y, Num) :-
	Xmax is (X+2)//3*3, Xmin is Xmax-2,
	between(Xmin, Xmax, X1),
	Ymax is (Y+2)//3*3, Ymin is Ymax-2,
	between(Ymin, Ymax, Y1),
	(Y1 \= Y; X1 \= X),
	getElement(Board, X1, Y1, Num1), Num1 == Num.

 /* 解を出力 */
output_solution(Board) :-
	write("solution:"), nl,
	output(Board).
 /* 盤面の現在の状態を出力 数が入っていないところは「_」と表示 */
output(Board) :-
	between(1, 9, Y),
	arg(Y, Board, Col),
	output_col(Col), fail.
output(_).
output_col(Col) :-
	between(1, 8, X),
	arg(X, Col, Elt),
	output_element(Elt), write(' '), fail.
output_col(Col) :-
	arg(9, Col, Elt), output_element(Elt), nl.
output_element(Elt) :-
	nonvar(Elt), write(Elt), !.
output_element(_) :-
	write('_').