「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。
列
1 2 3 4 5 6 7 8
*-----------------*
1 | Q . . . . . . . |
2 | . . . . Q . . . |
3 | . . . . . . . Q |
行 4 | . . . . . Q . . |
5 | . . Q . . . . . |
6 | . . . . . . Q . |
7 | . Q . . . . . . |
8 | . . . Q . . . . |
*-----------------*
図 : 8 クイーンの解答例
N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。まず最初に「8 クイーン」を解いてみて、そのあと N Queens Problem に挑戦することにしましょう。
8 クイーンを解くには、すべての置き方を試してみるしか方法はありません。最初のクイーンは、盤上の好きなところへ置くことができるので、64 通りの置き方があります。次のクイーンは 63 通り、その次は 62 通りあります。したがって、置き方の総数は 64 * 63 * ... * 57 = 178,462,987,637,760 通りもあります。
ところが、解答例を見ればわかるように、同じ行と列に 2 つ以上のクイーンを置くことはできません。上図の解答例を配列を使って表すと下図のようになります。
0 1 2 3 4 5 6 7 <-- 列の位置
---------------------------
[0, 6, 4, 7, 1, 3, 5, 2] <-- 要素が行の位置を表す
図 : リストでの行と列の表現方法
列を配列の添字に、行番号を要素に対応させれば、各要素には 0 から 7 までの数字が重複しないで入ることになります。すなわち、0 から 7 までの順列の総数である 8! = 40320 通りの置き方を調べればよいことになります。パズルを解く場合は、そのパズル固有の性質をうまく使って、生成するパターンの総数を減らすように工夫することが大切です。
あとは、生成した順列が 8 クイーンの条件を満たしているかチェックすればいいわけです。ポイントは斜めの利き筋のチェックです。次の図を見てください。
右斜め上の利き筋 左斜め上の利き筋
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
*-----------------* *-----------------*
|／／／／／／／／ | 8 -1 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 9 -2 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 10 -3 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 11 -4 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 12 -5 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 13 -6 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 14 -7 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | |＼＼＼＼＼＼＼＼ |
*-----------------* *-----------------*
x + y = constant x - y = constant
図 : 斜めの利き筋のチェック
斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になる、ということを利用すれば簡単にチェックできます。プログラムは次のようになります。
リスト : 斜め利き筋のチェック
function is_safe(b) {
for (let x = 1; x < b.length; x++) {
if (conflict(b, b[x], x)) return false;
}
return true;
}
関数 is_safe() の引数 b が盤面を表す配列です。is_safe() は x 列のクイーンが 0 から x - 1 列までのクイーンと衝突していないか、関数 conflict() を呼び出してチェックします。
最初は 1 列目のクイーンが 0 列のクイーンと衝突していないかチェックし、次に 2 列目のクイーンと 0, 1 列のクイーンをチェックします。このように、順番にクイーンをチェックしていき、最後に 7 列目のクイーンと 0 - 6 列のクイーンをチェックします。クイーン同士が衝突していたら false を返し、そうでなければ true を返します。
次は関数 conflict() を作りましょう。次のリストを見てください。
リスト : 衝突のチェック
function conflict(b, y, x) {
for (let x1 = 0; x1 < x; x1++ ) {
let y1 = b[x1];
if (x1 - y1 == x - y || x1 + y1 == x + y) return true;
}
return false;
}
関数 conflict() の引数 y がチェックするクイーンの行、x が列を表します。for ループで 0 列から x - 1 列のクイーンを取り出します。変数 x1 に列を、変数 y1 に行をセットします。あとはクイーン (x, y) と (x1, y1) の斜めの利き筋をチェックし、同じであれば衝突しているので true を返します。0 から x - 1 列のクイーンと衝突していなければ、最後に false を返します。
ここまで作ればあとは簡単です。8 クイーンを解くプログラムは次のようになります。
リスト : 8 クイーンの解法 (単純版)
function nqueen0(size) {
let c = 0;
const check = xs => {
if (is_safe(xs)) {
console.log(xs.toString());
c++;
}
}
permutation(check, size, iota(0, size));
console.log(c);
}
関数 nqueen0() の引数 size は盤面の大きさを表します。高階関数版の permutation() で順列を生成し、is_safe() で生成した盤面 xs が 8 クイーンの条件を満たしているかチェックします。そうであれば、console.log() で盤面 xs を出力します。
それでは実際に試してみましょう。
リスト : 実行
for (let size = 4; size <= 8; size++) {
console.log(`----- ${size} -----`);
nqueen0(size);
}
$ node nqueens.js ----- 4 ----- 1,3,0,2 2,0,3,1 2 ----- 5 ----- 0,2,4,1,3 0,3,1,4,2 1,3,0,2,4 1,4,2,0,3 2,0,3,1,4 2,4,1,3,0 3,0,2,4,1 3,1,4,2,0 4,1,3,0,2 4,2,0,3,1 10 ----- 6 ----- 1,3,5,0,2,4 2,5,1,4,0,3 3,0,4,1,5,2 4,2,0,5,3,1 4 ----- 7 ----- 0,2,4,6,1,3,5 0,3,6,2,5,1,4 0,4,1,5,2,6,3 ... 略 ... 6,2,5,1,4,0,3 6,3,0,4,1,5,2 6,4,2,0,5,3,1 40 ----- 8 ----- 0,4,7,5,2,6,1,3 0,5,7,2,6,3,1,4 0,6,3,5,7,1,4,2 ... 略 ... 7,1,4,2,0,6,3,5 7,2,0,5,1,4,6,3 7,3,0,2,5,1,6,4 92
nqueen0(8) を実行すると 92 通りの解が出力されます。
ところで、クイーンの個数を増やすと、プログラムの実行時間は極端に遅くなります。
リスト : N Queens Problem
// 実行
for (let size = 8; size <= 11; size++) {
console.log(`----- ${size} -----`);
var s = new Date().getTime();
nqueen0(size);
var e = new Date().getTime();
console.log(e - s);
}
nqueen0() は解を表示するのではなく、解の個数をカウントするように修正します。実行結果は次のようになりました。
表 : 実行結果 (時間 : 秒)
個数 : 8 : 9 : 10 : 11
-----+------+------+------+-------
解 : 92 : 352 : 724 : 2680
時間 : 0.06 : 0.21 : 2.19 : 22.05
実行環境 : Node.js (v22.12.0), Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
クイーンの個数をひとつ増やしただけでも、実行時間はとても遅くなります。実はこのプログラム、とても非効率なことをやっているのです。
実行速度が遅い理由は、失敗することがわかっている順列も生成してしまうからです。たとえば、最初 (0, 0) の位置にクイーンを置くと、次のクイーンは (1, 1) の位置に置くことはできませんね。したがって、[0, 1, X, X, X, X, X, X,] という配置はすべて失敗するのですが、順列を生成してからチェックする方法では、このような無駄を省くことができません。
そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。
リスト : N Queens Problem (高速化)
function nqueen1(fn, xs, ps = [], used = new Set()) {
if (ps.length == xs.length) {
fn([...ps]);
} else {
for (let x of xs) {
if (!used.has(x) && !conflict(ps, x, ps.length)) {
ps.push(x);
used.add(x);
nqueen1(fn, xs, ps, used);
used.delete(x);
ps.pop();
}
}
}
}
関数 nqueen1() は permutation() に conflict() の処理を付け加えただけです。これで無駄な順列の生成を省くことができます。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 8 : 9 : 10 : 11 : 12 : 13 : 14
-----+------+------+------+-------+-------+-------+--------
解 : 92 : 352 : 724 : 2680 : 14200 : 73712 : 365596
(0) : 0.06 : 0.21 : 2.19 : 22.05 : ----- : ----- : ------
(1) : ---- : ---- : 0.02 : 0.08 : 0.41 : 2.44 : 14.97
実行時間は速くなりましたが、クイーンの個数が 14 を超えると実行時間が極端に遅くなります。これは、斜めの利き筋をチェックする関数 conflict() の処理に時間がかかるからです。高速化に興味のある方は、拙作のページ Puzzle DE Programming: N Queens Problem をお読みくださいませ。
//
// nqueens.js : N Queens Problem
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import { iota, permutation } from './comb_func.js';
// 斜め利き筋のチェック
function conflict(b, y, x) {
for (let x1 = 0; x1 < x; x1++ ) {
let y1 = b[x1];
if (x1 - y1 == x - y || x1 + y1 == x + y) return true;
}
return false;
}
function is_safe(b) {
for (let x = 1; x < b.length; x++) {
if (conflict(b, b[x], x)) return false;
}
return true;
}
// 単純版
function nqueen0(size) {
let c = 0;
const check = xs => {
if (is_safe(xs)) {
// console.log(xs.toString());
c++;
}
}
permutation(check, size, iota(0, size));
console.log(c);
}
// 高速化
function nqueen1(fn, xs, ps = [], used = new Set()) {
if (ps.length == xs.length) {
fn([...ps]);
} else {
for (let x of xs) {
if (!used.has(x) && !conflict(ps, x, ps.length)) {
ps.push(x);
used.add(x);
nqueen1(fn, xs, ps, used);
used.delete(x);
ps.pop();
}
}
}
}
// 実行
for (let size = 8; size <= 14; size++) {
console.log(`----- ${size} -----`);
let c = 0;
var s = new Date().getTime();
nqueen1(xs => c++, iota(0, size));
var e = new Date().getTime();
console.log(c, e - s);
}
今回は「キュー (queue)」という基本的なデータ構造を作ってみましょう。たとえばチケットを買う場合、カウンタの前に並んで順番を待たなくてはいけません。キューはカウンタの前に並ぶ行列と考えてください。列の先頭にいる人から順番にチケットを買うことができますが、あとから来た人は列の後ろに並ばなくてはいけません。列の先頭まで進むと、チケットを購入することができます。これを表したのが下図です。
out in
──────────────
<= A B C D E . . . Z <=
──────────────
図 : キューの構造
このように、キューはデータを取り出すときは列の先頭から行い、データを追加するときは列の後ろへ行います。このため、キューは「待ち行列」とか「先入れ先出し (FIFO : first-in,first-out)」と呼ばれます。
キューの詳しい説明は拙作のページをお読みください。
//
// queue.js : キュー
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
// スタックを 2 つ使う方法
class Queue {
constructor() {
this._front = [];
this._rear = [];
}
// メソッド
length() { return this._front.length + this._rear.length; }
is_empty() { return this.length() == 0; }
is_full() { return false; }
clear() {
this._front = [];
this._rear = [];
}
enqueue(item) {
this._rear.push(item);
return item;
}
dequeue() {
if (this._front.length == 0) {
while (this._rear.length > 0) {
this._front.push(this._rear.pop());
}
}
return this._front.pop();
}
peek() {
let n = this._front.length;
return n > 0 ? this._front[n - 1] : this._rear[0];
}
}
// リングバッファ
class RingBuffer {
constructor(size) {
this._buff = new Array(size);
this._front = 0;
this._rear = 0;
this._cnt = 0;
this._size = size;
}
// メソッド
length() { return this._cnt; }
is_empty() { return this._cnt == 0; }
is_full() { return this._size == this._cnt; }
clear() {
this._front = 0;
this._rear = 0;
this._cnt = 0;
}
enqueue(item) {
if (!this.is_full()) {
this._buff[this._rear++] = item;
this._cnt++;
if (this._rear == this._size) this._rear = 0;
return item;
}
return;
}
dequeue() {
if (!this.is_empty()) {
let item = this._buff[this._front++];
this._cnt--;
if (this._front == this._size) this._front = 0;
return item;
}
return;
}
peek() {
return this.is_empty() ? undefined : this._buff[this._front];
}
}
export { Queue, RingBuffer };
//
// test_queue.js : キューのテスト
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import { Queue, RingBuffer } from './queue.js';
console.log("----- Queue -----");
var a = new Queue();
console.log(a.is_empty()); // true
console.log(a.is_full()); // false
console.log(a.length()); // 0
console.log(a.enqueue(10)); // 10
console.log(a.is_empty()); // false
console.log(a.is_full()); // false
console.log(a.length()); // 1
console.log(a.peek()); // 10
for (let x of [20,30,40]) a.enqueue(x);
console.log(a.dequeue()); // 10
console.log(a.peek()); // 20
for (let x of [50,60,70]) a.enqueue(x);
console.log(a.length()); // 6
while (!a.is_empty()) console.log(a.dequeue()); // 20, ..., 70
console.log(a.is_empty()); // true
console.log(a.is_full()); // false
console.log(a.length()); // 0
console.log("----- RingBuffer -----");
var b = new RingBuffer(6);
console.log(b.is_empty()); // true
console.log(b.is_full()); // false
console.log(b.length()); // 0
console.log(b.enqueue(10)); // 10
console.log(b.is_empty()); // false
console.log(b.is_full()); // false
console.log(b.length()); // 1
console.log(b.peek()); // 10
for (let x of [20,30,40]) b.enqueue(x);
console.log(b.dequeue()); // 10
console.log(b.peek()); // 20
for (let x of [50,60,70]) b.enqueue(x);
console.log(b.is_full()); // true
console.log(b.length()); // 6
while (!b.is_empty()) console.log(b.dequeue()); // 20, ..., 70
console.log(b.is_empty()); // true
console.log(b.is_full()); // false
console.log(b.length()); // 0
$ node test_queue.js ----- Queue ----- true false 0 10 false false 1 10 10 20 6 20 30 40 50 60 70 true false 0 ----- RingBuffer ----- true false 0 10 false false 1 10 10 20 true 6 20 30 40 50 60 70 true false 0
今回は簡単な例題として、地図上の A 地点から B 地点までの道順を求めるプログラムを作ってみましょう。「探索」にはいろいろな種類があります。たとえば、8 クイーン のようなパズルの解法も、あらゆる可能性の中から正解に行き着く手順を探すことですから、探索の一つと考えることができます。そして、探索でよく用いられる最も基本的な方法が「バックトラック (backtracking)」なのです。もちろん、経路の探索もバックトラックで解くことができます。
詳しい説明は拙作のページをお読みください。
Ｂ───Ｄ───Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ───Ｅ───Ｇ
図 : 経路図
//
// keiro.js : 経路の探索
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import { Queue } from './queue.js';
// 1 ----- 3 ----- 5
// / | |
// 0 | |
// \ | |
// 2 ----- 4 ----- 6
// 隣接リスト
const adjacent = [
[1, 2], // 0
[0, 2, 3], // 1
[0, 1, 4], // 2
[1, 4, 5], // 3
[2, 3, 6], // 4
[3], // 5
[4] // 6
];
// 深さ優先探索
function dfs(goal, path) {
let p = path[path.length - 1];
if (p == goal) {
console.log(path);
} else {
for (let q of adjacent[p]) {
if (path.indexOf(q) == -1) {
path.push(q);
dfs(goal, path);
path.pop();
}
}
}
}
// 実行
console.log('----- depth first search -----');
dfs(6, [0]);
// 幅優先探索
function bfs(start, goal) {
let q = new Queue();
q.enqueue([start]);
while (!q.is_empty()) {
let xs = q.dequeue();
let x = xs[xs.length - 1];
if (x == goal) {
console.log(xs);
} else {
for (let y of adjacent[x]) {
if (xs.indexOf(y) == -1) {
let ys = xs.concat([y]);
q.enqueue(ys);
}
}
}
}
}
console.log('----- breadth first search -----');
bfs(0, 6);
// 反復深化
function dfsi(path, goal, limit) {
if (path.length == limit) {
if (path[limit - 1] == goal) {
console.log(path);
}
} else {
for (let p of adjacent[path[path.length - 1]]) {
if (path.indexOf(p) == -1) {
path.push(p);
dfsi(path, goal, limit);
path.pop();
}
}
}
}
function ids(start, goal) {
for (let limit = 1; limit <= adjacent.length; limit++) {
console.log(`----- ${limit} -----`);
dfsi([start], goal, limit);
}
}
console.log('----- ids -----');
ids(0, 6);
$ node keiro.js ----- depth first search ----- [ 0, 1, 2, 4, 6 ] [ 0, 1, 3, 4, 6 ] [ 0, 2, 1, 3, 4, 6 ] [ 0, 2, 4, 6 ] ----- breadth first search ----- [ 0, 2, 4, 6 ] [ 0, 1, 2, 4, 6 ] [ 0, 1, 3, 4, 6 ] [ 0, 2, 1, 3, 4, 6 ] ----- ids ----- ----- 1 ----- ----- 2 ----- ----- 3 ----- ----- 4 ----- [ 0, 2, 4, 6 ] ----- 5 ----- [ 0, 1, 2, 4, 6 ] [ 0, 1, 3, 4, 6 ] ----- 6 ----- [ 0, 2, 1, 3, 4, 6 ] ----- 7 -----
ナイト (騎士) はチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │●│ │●│ │ │Ｋ│ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │●│ │●│ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
● : ナイト (K) が動ける位置 問題
問題 : 騎士の巡歴
このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。今回は 5 行 5 列の盤面でナイトの移動経路の総数を求めてください。
それではプログラムを作りましょう。盤面は 2 次元配列で表すことにします。この場合、騎士の移動手順は 5 行 5 列の盤面に記録したほうが簡単です。騎士が訪れていないマスを 0 とし、騎士の移動手順を 1 から始めれば、移動できるマスの判定を簡単に行うことができます。また、経路の出力も盤面を表示した方が直感的でわかりやすいかもしれません。
次は盤面の構成を考えましょう。単純な 5 行 5 列の 2 次元配列にすると、騎士が盤面から飛び出さないようにするため座標の範囲チェックが必要になります。このような場合、盤面の外側に壁を設定するとプログラムが簡単になります。
騎士は最大で 2 マス移動するので、壁の厚さも 2 マス用意します。したがって、盤面を表す配列は 9 行 9 列の大きさになります。壁に 0 以外の値 (-1) を設定しておけば、騎士が盤面から飛び出して壁の位置に移動しようとしても、盤面の値が 0 ではないので実際に移動することはできません。これで騎士を移動したときの範囲チェックを省略することができます。
//
// knight.js : 騎士の巡歴
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
// 盤面の初期化
function init_board() {
let board = [];
for (let i = 0; i < 9; i++) {
let xs = new Array(9);
xs.fill(-1);
board.push(xs);
}
for (let i = 2; i < 7; i++) {
for (let j = 2; j < 7; j++) {
board[i][j] = 0;
}
}
return board;
}
// 移動
const dx = [1, 2, 2, 1, -1, -2, -2, -1]
const dy = [-2, -1, 1, 2, 2, 1, -1, -2]
// 解の個数
var cnt = 0;
// 盤面の表示
function print_board(board) {
cnt++;
for (let i = 2; i < 7; i++) {
let xs = board[i];
console.log(xs.slice(2, 7).toString());
}
console.log("");
}
// 解法
function solver(board, x, y) {
let n = board[x][y];
if (n == 25) {
print_board(board);
} else {
for (let i = 0; i < 8; i++) {
let x1 = x + dx[i];
let y1 = y + dy[i];
if (board[x1][y1] == 0) {
board[x1][y1] = n + 1;
solver(board, x1, y1);
board[x1][y1] = 0;
}
}
}
}
function knight() {
let board = init_board();
board[2][2] = 1;
solver(board, 2, 2)
console.log(cnt);
}
// 実行
knight();
配列 dx は騎士の x 方向の変位、配列 dy は y 方向の変位を表します。現在の座標にこの値を加えることで、次の座標を決定します。配列 board は盤面を表します。関数 init_board() で、壁の部分は -1 に、実際の盤面は 0 に初期化しておきます。
関数 solver() は引数として盤面 board と騎士の座標 x, y を受け取ります。まず、board[x][y] から手数を取り出して変数 n にセットします。n == 25 であれば、騎士はすべてのマスを訪れたので、print_board() で盤面を出力します。
そうでなければ、次に移動するマスを選びます。for 文で dx と dy の要素を取り出して x と y の値に加え、solver() を再帰呼び出しします。再帰呼び出しから戻ってきたら、board[x1][y1] の値を 0 に戻すことをお忘れなく。あとはとくに難しいところはないと思います。
実行結果は次のようになりました。
$ node knight.js 1,16,21,10,25 20,11,24,15,22 17,2,19,6,9 12,7,4,23,14 3,18,13,8,5 1,16,19,10,25 18,11,24,15,20 23,2,17,6,9 12,7,4,21,14 3,22,13,8,5 ・・・省略・・・ 1,16,11,6,3 10,5,2,21,12 15,22,17,4,7 18,9,24,13,20 23,14,19,8,25 1,16,11,6,3 10,5,2,17,12 15,22,19,4,7 20,9,24,13,18 23,14,21,8,25 304
解は全部で 304 通りあります。
参考文献『世界のパズル百科イラストパズルワンダーランド』によると、15 パズルはアメリカのサム・ロイドが 1870 年代に考案したパズルで、彼はパズルの神様と呼ばれるほど有名なパズル作家だそうです。
┌─┬─┬─┬─┐
│１│２│３│４│
├─┼─┼─┼─┤
│５│６│７│８│
├─┼─┼─┼─┤
│９│10│11│12│
├─┼─┼─┼─┤
│13│14│15│ │
└─┴─┴─┴─┘
図 : 15 パズル
15 パズルは上図に示すように、1 から 15 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を跳び越したり持ち上げたりすることはできません。
15 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、16! (約 2e13) 通りもあります。実際には、15 パズルの性質からその半分になるのですが、それでもパソコンで扱うにはあまりにも大きすぎる数です。そこで、盤面を一回り小さくした、1 から 8 までの数字を並べる「8 パズル」を考えることにします。
┌─┬─┬─┐ ┌─┬─┬─┐
│１│２│３│ │１│２│３│
├─┼─┼─┤ ├─┼─┼─┤
│４│５│６│ │４│５│６│
├─┼─┼─┤ ├─┼─┼─┤
│７│８│ │ │８│７│ │
└─┴─┴─┘ └─┴─┴─┘
（１）完成形 （２）不可能な局面
図 : 8 パズル
15 パズルは 4 行 4 列の盤ですが、8 パズルは 3 行 3 列と盤を小さくしたパズルです。8 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、9! = 362880 通りあります。15 パズルや 8 パズルの場合、参考文献『特集コンピュータパズルへの招待 スライディングブロック編』によると 『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にしか移行できない』 とのことです。
上図 (2) は 7 と 8 を入れ替えただけの配置です。この場合、交換の回数が奇数回のため完成形に到達することができない、つまり解くことができないのです。このような性質を「偶奇性（パリティ）」といいます。詳しい説明は拙作のページ「Puzzle DE Programming: 偶奇性（パリティ）のお話」をお読みください。8 パズルの場合、完成形に到達する局面の総数は 9! / 2 = 181440 個となります。
8 パズルの詳しい説明は拙作のページをお読みください。
//
// eight.js : 8 パズル
//
// Copyright (c) 2025 Makoto Hiroi
//
// Released under the MIT license
// https://opensource.org/license/mit/
//
import { Queue } from './queue.js';
// 盤面
// 0 1 2
// 3 4 5
// 6 7 8
// 隣接リスト
const adjacent = [
[1, 3], // 0
[0, 2, 4], // 1
[1, 5], // 2
[0, 4, 6], // 3
[1, 3, 5, 7], // 4
[2, 4, 8], // 5
[3, 7], // 6
[4, 6, 8], // 7
[5, 7] // 8
];
// 駒の移動
function move_piece(board, p, s) {
let nb = [...board];
nb[s] = nb[p];
nb[p] = 0;
return nb;
}
// 同じ盤面か？
function equal(xs, ys) {
for (let i = 0; i < xs.length; i++) {
if (xs[i] != ys[i]) return false;
}
return true;
}
// 手順の表示
function print_answer(st) {
if (st != null) {
let {board: b, prev: ps} = st;
print_answer(ps);
console.log(b.toString());
}
}
// 幅優先探索
function bfs(start, goal) {
let que = new Queue();
let tbl = new Set();
que.enqueue({board: start, space: start.indexOf(0), prev: null});
tbl.add(start.toString());
while (!que.is_empty()) {
let st = que.dequeue();
let {board: b, space: s} = st;
if (equal(b, goal)) {
print_answer(st);
return true;
}
for (let x of adjacent[s]) {
let newb = move_piece(b, x, s);
let key = newb.toString();
if (!tbl.has(key)) {
let newst = {board: newb, space: x, prev: st};
tbl.add(key);
que.enqueue(newst);
}
}
}
return false;
}
// 実行
bfs([8,6,7,2,5,4,3,0,1],[1,2,3,4,5,6,7,8,0]);
$ node eight.js 8,6,7,2,5,4,3,0,1 8,6,7,2,0,4,3,5,1 8,0,7,2,6,4,3,5,1 0,8,7,2,6,4,3,5,1 2,8,7,0,6,4,3,5,1 2,8,7,3,6,4,0,5,1 2,8,7,3,6,4,5,0,1 2,8,7,3,6,4,5,1,0 2,8,7,3,6,0,5,1,4 2,8,0,3,6,7,5,1,4 2,0,8,3,6,7,5,1,4 2,6,8,3,0,7,5,1,4 2,6,8,0,3,7,5,1,4 2,6,8,5,3,7,0,1,4 2,6,8,5,3,7,1,0,4 2,6,8,5,3,7,1,4,0 2,6,8,5,3,0,1,4,7 2,6,0,5,3,8,1,4,7 2,0,6,5,3,8,1,4,7 2,3,6,5,0,8,1,4,7 2,3,6,0,5,8,1,4,7 2,3,6,1,5,8,0,4,7 2,3,6,1,5,8,4,0,7 2,3,6,1,5,8,4,7,0 2,3,6,1,5,0,4,7,8 2,3,0,1,5,6,4,7,8 2,0,3,1,5,6,4,7,8 0,2,3,1,5,6,4,7,8 1,2,3,0,5,6,4,7,8 1,2,3,4,5,6,0,7,8 1,2,3,4,5,6,7,0,8 1,2,3,4,5,6,7,8,0