js数独ソルバ解説
前準備
配列の要素を扱うメソッドについて
今回のコードでは以下のメソッドを利用しています。
Array
map
配列のそれぞれの要素に対して関数を実行し、その戻り値からなる新たな配列を返します
filter
配列のそれぞれの要素に対して関数を実行し、trueとなる要素だけからなる新たな配列を返します
every
配列のそれぞれの要素に対して関数を実行し、一つでもfalseが見つかればfalseを返し、それ以外ではtrueを返します
some
配列のそれぞれの要素に対して関数を実行し、一つでもtrueが見つかればtrueを返し、それ以外ではfalseを返します
code: sudoku_solver.js
const board = "530070000600195000098000060800060003400803001700020006060000280000419005000080079".split('').map(_=>parseInt(_));
"".split('').map(_=>parseInt(_))
で文字列を1文字ごとに区切って配列にしています。配列の値は数値型に変換します。
数独のマスを左上から右方向に読み、右下へと向かう一次元の配列として管理しています。
1-9は既に数字が入っているマス、0は空白マスを表しています
code: sudoku.js
// グループ関数
const groups = [
(i)=> i/9|0,
(i)=> i%9,
(i)=> (i/27|0)*3+(i%9/3)|0
];
数独の制約を示す関数が入る配列です。
マスの座標(0-80)を渡した時に、同じグループに入る者同士が同じ値を返します。
JavascriptにはPythonの//演算子のような、整数除算に相当する演算子がないので
Math.floor(i/b)
i/b|0
etc
のようにして整数に変換する必要があります。
それぞれ
横方向が一致しているか
縦方向が一致しているか
3x3のブロックが一致しているか
を示しています。
code: sudoku.js
// 配列に値の重複がないかを確認
const isUnique = (arr1) => arr1.every((e1,i,arr2)=> !arr2.some((e2,j) => j != i && e1 == e2));
// 指定したグループ, グループ関数の重複チェック
// 盤面から指定したグループの埋まっているマスを抽出し、isUnique関数で重複チェック
const checkUnique = (n,g) => isUnique(board.filter((e,i) => g(i) == n && e > 0));
// 指定した座標(0-80)に対して、各グループ関数が制約を満たしているか
const checkCell = (i) => groups.every(g => checkUnique(g(i),g));
数独のルールを満たしているかを判定する関数群です。
code: sudoku.js
const solve = index => index < 81
return checkCell(index) && solve(index + 1);
}) ? 1 : boardindex = 0)) : true;
数独の解をバックトラック法で求めるコードです。
3項演算子が3重にネストしています。
わかりやすくするために、3項演算子をCoffeeScriptのようなIf式に直すとこうなります。
code: sudoku.coffee
const solve = index =>
if index < 81
then solve(index + 1)
return checkCell(index) && solve(index + 1);
}) then true else boardindex = 0)) else true;
現在のindexを引数として取得
indexが81未満であれば
盤面のindexが0であれば
1〜9までの数字について下記の操作を行なった結果がtrueであれば、trueを返す
indexのマスををその数字に替える
indexのマスが条件を満たしていれば、一つ先のindexに対して再帰的に処理を実行した結果を取得
(ショートサーキット評価になっているので、条件チェックが満たされている時しか再帰的な処理は行われない)
そうでなければ、indexのマスを0に戻し, falseを返す。
そうでなければ
一つ先のindexに対して再帰的に処理を実行した結果を取得
そうでなければ
trueを返す
code: sudoku.js
solve(0);
上記の関数をindex:0から順に実行すれば、左上から順に数字が入るか仮定してゆき、一つ解を見つけるか、どの組み合わせも成立しなかった時に停止します。
code: sudoku.js
console.log(board.join(''));
停止したときの盤面を、一行につなげて出力します。
おまけ
上記のコードを圧縮すると80文字4行で入力を受け取り数独の解を出力するhtmlになります。
code: sudoku.html
<script>p=location.hash.split('').map(_=>_-0).slice(1),k=n=>[_=>(_/27|0)*3+_%9/
3|0,_=>_/9|0,_=>_%9].every(g=>p.filter((e,i)=>g(i)==g(n)&&e).every((e,i,a)=>!a
.some((f,j)=>j-i&&e==f))),(l=i=>i-81?pi?l(i+1):1,2,3,4,5,6,7,8,9.some(_=>(p i=_,k(i)&&l(i+1)))?1:pi=0:1)(0);document.write(p.join(''))</script>