This is between us.

ナンプレは機械的に答えを出せそうだと思いついたので、アルゴリズムの作成を試してみました。言語はPHPです。PHP習得のためにPHPを使って書いただけなので，PHPである必要性は特にありません。
思いつきの動作でパッと組んだので、おそらくかなり非効率的な処理を行っています。

ナンプレ(数独)のルール

9×9のマスに数値を当てはめていく。
縦、横に1~9のすべての数が一つずつ入る。(一つの行、一つの列で重複する数値が存在しない)
全体を3×3マスの塊で9分割したとき、塊の中のマスに1~9のすべての数が一つずつ入る。

スポンサーリンク

アルゴリズムの考案

バックトラック法というアルゴリズムを参考にしました。
とり得る値を仮に代入し、マスを埋めていく。 条件を満たすようにマスを埋められなくなったら前に戻り、他の数値を当てはめていく。これを繰り返すことで答えとなる数値を見つけるという方法です。簡単に言えば条件に当てはまる数値で総当たり、といったところでしょうか。

必要な処理の予想

・空いているマスを見つける。
・マスに入る可能性のある数値を探す。
・マスに数値を入れる。
・最終チェック処理(ルールに違反している場所がないか)。
・完成した表の表示。
こんな感じでしょう。とりあえず動かすことを目的としていたので単純にこれで組むことにしました。

メイン処理

大本となる処理です。空いているマスを探し、あれば置ける数値を探し、ないときはチェックを行い問題なければ表示、という流れになっています。
再帰関数にすることによって、条件に合うように数値を入れられなくなると、一つ前のマスに戻り数値を変えるような動きをします。
X_MAX、Y_MAXは最大値を表す定数で、9×9マスなのでどちらも9です。
マスの座標は81個の要素を持つ配列で表現することとし、$fieldという名の変数にしました。空いているマスは0で表現することにしています。
マスの座標の指定にはx,yというキーを持つ連想配列で表現しました。 単純な変数にしなかったのは、返り値で座標を渡すときに一変数でないと面倒だろうと思ったからです。

function sudoku($field, $point) {
	// 空いているマスの探索
	$point = findEmptyPoint($field, $point);
	//空いているマスがないとき
	if($point["x"]*$point["y"] == X_MAX*Y_MAX){
	        //ルールに反していないかチェック
		if(checkField($field)){
			printField($field);
		}
		return;
	}
	for($num=1; $num<=9; $num++){
		//$numが$pointに置けるか
		if(putJudge( $field, $point, $num)){
			$field[X_MAX * $point["y"] + $point["x"]] = $num;
			//再帰
			sudoku($field, $point);
		}
	}
}

空いているマスを探す処理

空いているマスを探します。これは単純で、二重ループで空いているマスを見つけるまで配列の中身を調べているだけです。

function findEmptyPoint($field, $point){
	while ( $point["y"] < Y_MAX ) {
		while ( $point["x"] < X_MAX ) {
			if ($field [X_MAX * $point["y"] + $point["x"]] == 0) {
				return $point;
			}
			$point["x"]++;
		}
		$point["x"]=0;
		$point["y"]++;
	}
	$point["x"]=X_MAX;
	return $point;
}

値がマスに入れられるかチェックする処理

引数として与えられたマスの座標に、同じく引数として与えられた数値を入れられるかをチェックし、入れられればtrueを返します。
$numlistという配列でどの数値が既に存在しているかを管理しています。
最初のfor文では横の列に存在する数値、次のfor文で縦の列に存在する数値、最後のfor文で3×3のブロックに存在する数値を確認しています。
floor()というのは切り捨ての数値を取得する関数です。これを使うことで自分の所属する3×3マスの数値を正しく取得することができます。
マスにある数値をそのまま$numlistの要素番号として使うのはあまりよろしくないですが、個人で使う分にはまあ問題はないでしょう。

function putJudge($field, $point, $num) {
	$numlist = array_fill( 0, 10, 0 );

	for($i = 0; $i < 9; $i++) {
		$numlist[$field [X_MAX * $point["y"] + $i]] = 1;
	}
	for($i = 0; $i < 9; $i++) {
		$numlist[$field [X_MAX * $i + $point["x"]]] = 1;
	}
	for($i = 0; $i < 3; $i++) {
		for($j = 0; $j < 3; $j ++) {
			$numlist[$field [X_MAX * (floor ( $point["y"] / 3 ) * 3 + $i)
						 + floor ( $point["x"] / 3 ) * 3 + $j]] = 1;
		}
	}

	if($numlist[$num]!=1){
		return true;
	}
	return false;
}

最終チェック処理

最後にすべてのマスで条件を満たしているかチェックを行います。putJudge()関数をそのまま流用しています。
そもそも条件に当てはまらない数値で完全に埋まることはないのでこの処理がいるかは疑問ですが、念のために付けておきました。

function checkField($field){
	for($i=0; $i<Y_MAX; $i++){
		for($j=0; $j<X_MAX; $j++){
			if(putJudge($field, array("x"=>$j, "y"=>$i), $field [X_MAX * $i + $j])){
				return false;
			}
		}
	}
	return true;
}

表示処理

表示を行います。特に説明することはありません。
装飾などはほとんど行っていない状態です。

function printField($field){
	echo "<p>";
	for($i = 0; $i < 9; $i ++) {
		for($j = 0; $j < 9; $j ++) {
			echo $field [X_MAX * $i + $j] . "&nbsp;";
		}
		echo "<br />";
	}
	echo "</p>";
}

実演

実際に動かすため、適当に数独の問題を与えてみます。あまり難しいものだと処理に時間がかかります。

$field = array(0, 0, 0, 0, 2, 7, 0, 0, 8,
	       0, 0, 1, 0, 0, 0, 0, 0, 7,
	       0, 6, 4, 0, 0, 5, 0, 1, 9,
	       2, 7, 0, 9, 6, 3, 1, 5, 4,
	       4, 0, 0, 2, 7, 0, 6, 8, 3,
	       6, 1, 3, 0, 0, 4, 0, 0, 0,
	       0, 8, 7, 6, 3, 2, 0, 4, 1,
	       0, 9, 0, 0, 4, 8, 0, 0, 5,
	       3, 4, 2, 5, 1, 9, 8, 7, 0 
	      );

こうなります。(計算前の表と文字は自前でつけたものです。計算前の表はprintField()に突っ込めば表示が楽です。)ナンプレを解くことに成功しました。

before
0 0 0 0 2 7 0 0 8 
0 0 1 0 0 0 0 0 7 
0 6 4 0 0 5 0 1 9 
2 7 0 9 6 3 1 5 4 
4 0 0 2 7 0 6 8 3 
6 1 3 0 0 4 0 0 0 
0 8 7 6 3 2 0 4 1 
0 9 0 0 4 8 0 0 5 
3 4 2 5 1 9 8 7 0 

after
9 3 5 1 2 7 4 6 8 
8 2 1 4 9 6 5 3 7 
7 6 4 3 8 5 2 1 9 
2 7 8 9 6 3 1 5 4 
4 5 9 2 7 1 6 8 3 
6 1 3 8 5 4 7 9 2 
5 8 7 6 3 2 9 4 1 
1 9 6 7 4 8 3 2 5 
3 4 2 5 1 9 8 7 6 

もう少し面倒な探索を行うことを予想していましたが、再帰が少し入ってきたくらいで簡単なもので済ますことができましたね。 ちなみに表示を終えた後も処理を続行するため、複数解がある場合すべて検索します。