最近、シンガポールのリー・シェンロン首相が数独ソルバープログラムを公開したという話がありました(拡張子がcppなだけのCのコードとは思うが)。
Qiita初投稿として、ECME-262 6th Edition, The 2015 ECMAScript Language Specification(いわゆるES6)のgenerator構文を使った10行の数独ソルバーについて書いてみます。
数独ソルバー(解のジェネレータ)のコード
var solve = function* solve(b, i) {
if (i === 81) return yield b;
if (b[i] !== 0) return yield* solve(b, i + 1);
var used = b.filter(function (_, j) {
return (i % 9) === (j % 9) || (0|i / 9) === (0|j / 9) ||
(0|i / 27) === (0|j / 27) && (0|i % 9 / 3) === (0|j % 9 / 3);
});
for (var v = 1; v <= 9; v++) if (used.indexOf(v) === -1)
yield* solve(b.slice(0, i).concat([v]).concat(b.slice(i + 1)), i + 1);
};
solve(b, i)は、bは解く数独盤で、1から9の値または空欄として0が入った81要素の配列で、iは数独盤のカーソル値で0を入れて、呼び出します。戻り値のジェネレータは、bと同じ構造の解を列挙しつくします。
// example case from http://rosettacode.org/wiki/Sudoku
var problem = [
8, 5, 0, 0, 0, 2, 4, 0, 0,
7, 2, 0, 0, 0, 0, 0, 0, 9,
0, 0, 4, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 7, 0, 0, 2,
3, 0, 5, 0, 0, 0, 9, 0, 0,
0, 4, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 8, 0, 0, 7, 0,
0, 1, 7, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 3, 6, 0, 4, 0
];
for (var solution of solve(problem, 0)) {
console.log(solution);
}
数独ソルバーのアルゴリズム
解を出し尽くすジェネレータではない、単一の解を返す関数としての数独ソルバーは以下のコードになります。(リー首相のコードでのアルゴリズムとは違い、効率より単純さを優先しているものです)。ジェネレータでの10行ソルバーは、このアルゴリズムから解を複数化しただけのものです。
var solve = function solve(board, i) {
if (i === 81) return board; // <= 盤面上の欄が全部埋まっているので正解
if (board[i] !== 0) return solve(board, i + 1); // 空欄ではないのでスキップ
// (以下は、iが空欄の時の処理)
// iの欄と、同一の行、同一の列、同一のブロックの欄全部の中で使われてる値のリスト
var used = board.filter(function (_, j) {
var isSameColumn = (i % 9) === (j % 9);
var isSameRow = (0|i / 9) === (0|j / 9);
var isSameBlockRow = (0|i / 27) === (0|j / 27);
var isSameBlockColumn = (0|i % 9 / 3) === (0|j % 9 / 3);
var isSameBlock = isSameBlockRow && isSameBlockColumn;
return isSameColumn || isSameRow || isSameBlock;
});
// before, after: boardのiの前後
var before = board.slice(0, i), after = board.slice(i + 1);
for (var v = 1; v <= 9; v++) { // iの欄にはめ込む値
if (used.indexOf(v) !== -1) continue; // vがused中にあった場合スキップ
// iの位置にvを入れた数独盤
var nextboard = before.concat([v]).concat(after);
var r = solve(nextboard, i + 1); // nextboardでソルバーを実行
if (r) return r; // 再帰呼び出しに解があればそれを返す
}
return null; // 引数のboardでは正解がなかった
};
// 実行例
console.log(solve(problem, 0));
擬似コードにすると、以下のようになります:
- 盤面上の欄を0から順に最後まで順にたどる
- 最後まで到達してたら、正解としてその盤面を返す
- 現欄が空欄でなければ、次の欄にすすむ
- 現空欄と、同行、同列、同ブロックになる全欄に入ってる数値の利用済み数リストを作る
- 数値を1から9まで順にたどって、その数値が利用済み数の中にない場合、
- この数値を現空欄に入れた新盤面をつくる
- この新盤面を使って、再帰的にソルバーを呼び出す
- もし再帰ソルバーが解を返せば、それを正解として返す
- (これ以上は盤面には正解はない)
盤面のインデックスiと、行番号や列番号との関係は以下になります:
- 列番号(0,1,2,3,...,8):
i % 9(= 9で割った余り) - 行番号(0,1,2,3,...,8):
i / 9の整数部(= 9で割った値) - 3x3ブロックの行番号(0,1,2):
i / 27の整数部(= 行番号 / 3の整数部) - 3x3ブロックの列番号(0,1,2):
(i % 9) / 3の整数部(= 列番号 / 3の整数部)
この関係を用いて、同行、同列、同ブロックの欄全部を集めたリストがusedになっています。
各欄ごとにusedを再計算するのではなく、(boardと同様に)各々の行や列やブロックごとの利用済み値の一覧を保持更新して利用すれば、リー首相のアルゴリズムのようになるでしょう。
ES6で拡張されたジェネレータ向け構文一覧
-
function* GENERATOR(...) {...}: ジェネレータの定義 -
for (var V of GENERATOR(...)) {...}: ジェネレータの走査(for-ofループ) -
yield VALUE: ジェネレータ走査でVALUEを渡す -
yield* GENERATOR(...): ジェネレータの移譲-
for (var V of GENERATOR(...)) yield V;とほぼ等価(yield*は式だが、for-ofループは文である)
-
ソルバー関数のジェネレータ化
単一の値を返す関数をジェネレータ化して、複数の解を返すようにするには、
以下の手法で書き換えていきます:
- 関数
function=> ジェネレータfunction* - 解を返す
return board=>yield boardにする - 再帰呼び出し
solve(board, i + 1)=>yield* solve(board, i + 1)として、
再帰的なジェネレータ移譲を行う - ループ内の再帰ソルバー呼び出しのあとでも
returnでループを止めない
これらを適用すると、以下のジェネレータへと変換されます:
var solve = function* solve(board, i) {
if (i === 81) {
yield board; // <= 盤面上の欄が全部埋まっているので正解
return;
}
if (board[i] !== 0) {
yield* solve(board, i + 1); // 空欄ではないのでスキップ
return;
}
// iの欄と、同一の行、同一の列、同一のブロックの欄全部の中で使われてる値のリスト
var used = board.filter(function (_, j) {
var isSameColumn = (i % 9) === (j % 9);
var isSameRow = (0|i / 9) === (0|j / 9);
var isSameBlockRow = (0|i / 27) === (0|j / 27);
var isSameBlockColumn = (0|i % 9 / 3) === (0|j % 9 / 3);
var isSameBlock = isSameBlockRow && isSameBlockColumn;
return isSameColumn || isSameRow || isSameBlock;
});
// before, after: boardのiの前後
var before = board.slice(0, i), after = board.slice(i + 1);
for (var v = 1; v <= 9; v++) { // iの欄にはめ込む値
if (used.indexOf(v) !== -1) continue; // vがused中にあった場合スキップ
// iの位置にvを入れた数独盤
var nextboard = before.concat([v]).concat(after);
yield* solve(nextboard, i + 1); // nextboardでソルバーを実行
//// returnしないで、全部の値で再帰ソルバーを実行する
}
return; //// generatorのreturn値は、for-ofやyield*では利用されない
};
// 実行例
for (var solution of solve(problem, 0)) {
console.log(solution);
}
このコードをさらに縮めていくことで、上述の10行ソルバーのコードとなります。ただし縮めた結果は等価ではなく、実行効率も犠牲にしています。
ソースコード
ES6 generatorが機能するiojsで実行可能な、出力整形込みの完全なコードを以下に置いています:
リファレンス
以下のリンクは、いくつかの言語での数独ソルバーの最短コードゴルフ(ちなみに、コード内によく出る48はASCIIの"0")
以下のリンクは、各言語での典型的な数独ソルバーのコード一覧(現時点では、JavaScriptのコードはない)