Sudoku solver

Problem
Answer
Log



Problem link:



Preset problems



Data structure

盤面配列 int[]
	答えとなる配列
	マスID→(確定してたらその数字 else -1)

候補配列 int[]
	そのマスに入る数字の候補集合
	マスID→論理和( i があり得るなら 1<<(i-1) )
		(example) 候補が 1 か 2 の場合、0x03

仮定レコード { 仮定マス : int, 仮定した数字 : int, 残りマス数 : int, 盤面配列 : int[], 候補配列 : int[] }
	どこかのマスをえいやっと適当な数字に(仮に)確定しないと進まなくなったとき、仮定前の状態を保存する構造体(JavaScriptだとハッシュというのかしら)

仮定スタック
	仮定レコードを積み上げていく場所。
	仮定が必要になったとき、push
	現在の仮定が破綻したとき、pop

Algorithm

くりかえす
	#候補を絞る処理
	空白マスそれぞれについて
		タテ、ヨコ、所属ブロックの確定マスにある数字を自分の候補から消す
		候補が 0 個になったら矛盾フラグON、ループ脱出
	
	全部確定してたら終了
	
	if 矛盾フラグ == ON
		#最後に仮定した内容が間違っていた
		while
			仮定スタックからpopした盤面と候補を現在の盤面と候補に上書きする
			次の候補 = 最後に仮定したマスについて、最後に仮定した数字の次の候補
			次の候補があったらループ脱出
	else
		#新規にどこかを何かに仮定する
		最も候補が少ないマスをみつける
		次の候補 = 候補の最初の数字
	
	#仮定する処理
	仮定レコード作成。仮定したマス、仮定した数字、盤面、候補を仮定レコードに書き込む
	盤面に仮定を追加する

2007/12/11(Tue) 00:57:54 Koji Hara