４＊４のスライドパズルをJavaScriptで自動解答させようとしたら帰ってこなくなった


# 調子に乗って４＊４のパズルAIに解いてもらおうとしたら、探索から帰ってこなくなった( ﾟДﾟ)

- 改良版で、速く帰って来る場合

![20250427_slide_puzzle_size_4_03.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3562068/f9515b78-88ef-4b95-886b-6390b565e18a.gif)


- 改良版でもそこそこかかる場合

![20250427_slide_puzzle_size_4_01.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3562068/efe052d3-e4c3-492e-b5ac-fe2e9cdf8ac3.gif)


## 背景
前回作った正式名称良く分からないパズルですが、
３＊３を作ったなら、まあ４＊４も作るでしょう、という軽い気持ちでたった1サイズの拡張を作成し、
そして当然自力だと全然解けないのでスクリプテッドAIにお願いしたら、、
画面固まった？
リロードも効かない？
開発者ツールでコンソールログ見ると、、、動いてる。
めっちゃ探索してる。
でも、、、何分待っても帰ってこない( ﾟДﾟ)

## 理由と対処
探索から帰ってこないのは、何も考えずに既存のアルゴリズムで、４＊４の探索をお願いした私の落ち度でした。
画面が固まったのは、探索のループを同期処理で待っていた私の落ち度でした。
対処は、アルゴリズムの変更、非同期処理の採用です。
これでもまだ現実的な時間で帰ってこないこともありますが、一旦ここで完成とします。

---

# デモ
どのバージョンの自動解答も、状態によっては長時間応答しなくなるので、
中止する場合は戻るボタンか、ブラウザのタブを閉じて終了してください。

https://kubo-4ka.github.io/slide-puzzle-size-4/

# ソース

https://github.com/kubo-4ka/slide-puzzle-size-4/

# 前回記事

https://qiita.com/kubo4ka/items/8e68d9c6c76fef03958e

https://qiita.com/kubo4ka/items/3f38a5fbf8e9755d54d5

---

# 4×4スライドパズル自動解答 実装変遷まとめ

## ① A*アルゴリズム＋同期処理版（v301→v401）

<details><summary>diff</summary>

```diff
diff -u v301_script.js v401_script.js
--- v301_script.js      2025-04-27 22:59:35.694709700 +0900
+++ v401_script.js      2025-04-27 23:00:13.093500100 +0900
@@ -5,9 +5,14 @@
 const timerLabel = document.getElementById("timer");
 const clearMessage = document.getElementById("clearMessage");

+// パズルサイズとタイル数を定義
+const SIZE = 4;
+const shuffleTimes = 40;
+const TILE_COUNT = SIZE * SIZE;
+
 // パズル状態管理用変数
 let tiles = [];
-let emptyIndex = 8;
+let emptyIndex = TILE_COUNT - 1;
 let tileElements = {};
 let startTime = null;
 let timerInterval = null;
@@ -17,9 +22,9 @@

 // タイルを初期化
 function createTiles() {
-  tiles = [...Array(8).keys()].map(n => n + 1);
+  tiles = [...Array(TILE_COUNT - 1).keys()].map(n => n + 1);
   tiles.push(null);
-  emptyIndex = 8;
+  emptyIndex = TILE_COUNT - 1;
   initRender();
 }

@@ -56,7 +61,8 @@

 // インデックスからCSS transform値を算出
 function getTransform(i) {
-  return `translate(${(i % 3) * 85}px, ${Math.floor(i / 3) * 85}px)`;
+  const step = 255 / SIZE;
+  return `translate(${(i % SIZE) * step}px, ${Math.floor(i / SIZE) * step}px)`;
 }

 // 指定タイルを移動
@@ -65,8 +71,8 @@
   const index = tiles.indexOf(num);
   const diff = Math.abs(index - emptyIndex);
   const valid =
-    (diff === 1 && Math.floor(index / 3) === Math.floor(emptyIndex / 3)) ||
-    diff === 3;
+    (diff === 1 && Math.floor(index / SIZE) === Math.floor(emptyIndex / SIZE)) ||
+    diff === SIZE;

   if (valid) {
     console.log(`[Move] ${num} (${index}) → empty (${emptyIndex})`);
@@ -79,7 +85,7 @@

 // クリア判定
 function checkClear() {
-  for (let i = 0; i < 8; i++) {
+  for (let i = 0; i < TILE_COUNT - 1; i++) {
     if (tiles[i] !== i + 1) return false;
   }
   console.log(`[Game] CLEAR`);
@@ -98,18 +104,18 @@
 }

 // タイルをランダムにシャッフル
-function shuffle(times = 20, onComplete = () => {}) {
+function shuffle(times = shuffleTimes, onComplete = () => {}) {
   console.log(`[Shuffle] START (${times} times)`);
   let count = 0;
   let previousEmptyIndex = -1;

   const interval = setInterval(() => {
-    const moves = [1, -1, 3, -3];
+    const moves = [1, -1, SIZE, -SIZE];
     const possible = moves
       .map(d => emptyIndex + d)
       .filter(i =>
         i >= 0 &&
-        i < 9 &&
+        i < TILE_COUNT &&
         i !== previousEmptyIndex &&
         moveAllowed(emptyIndex, i)
       );
@@ -141,7 +147,7 @@
 // 指定2インデックス間の移動可否判定
 function moveAllowed(from, to) {
   const diff = Math.abs(from - to);
-  return (diff === 1 && Math.floor(from / 3) === Math.floor(to / 3)) || diff === 3;
+  return (diff === 1 && Math.floor(from / SIZE) === Math.floor(to / SIZE)) || diff === SIZE;
 }

 // スタートボタン押下時の処理
@@ -156,7 +162,7 @@
   createTiles();

   setTimeout(() => {
-    shuffle(20, () => {
+    shuffle(shuffleTimes, () => {
       startBtn.textContent = "Trying...";
       helpBtn.disabled = false;
     });
@@ -165,16 +171,16 @@

 // A*探索
 function solvePuzzle(initialTiles) {
-  const goal = [...Array(8).keys()].map(n => n + 1).concat(null);
+  const goal = [...Array(TILE_COUNT - 1).keys()].map(n => n + 1).concat(null);

   // マンハッタン距離の計算
   function manhattan(state) {
     let dist = 0;
-    for (let i = 0; i < 9; i++) {
+    for (let i = 0; i < TILE_COUNT; i++) {
       const val = state[i];
       if (val === null) continue;
       const goalIndex = val - 1;
-      dist += Math.abs(i % 3 - goalIndex % 3) + Math.abs(Math.floor(i / 3) - Math.floor(goalIndex / 3));+      dist += Math.abs(i % SIZE - goalIndex % SIZE) + Math.abs(Math.floor(i / SIZE) - Math.floor(goalIndex / SIZE));
     }
     return dist;
   }
@@ -183,13 +189,13 @@
   function getNeighbors(state) {
     const neighbors = [];
     const empty = state.indexOf(null);
-    const directions = [1, -1, 3, -3];
+    const directions = [1, -1, SIZE, -SIZE];
     for (const d of directions) {
       const target = empty + d;
       if (
-        target < 0 || target >= 9 ||
-        (d === 1 && Math.floor(empty / 3) !== Math.floor(target / 3)) ||
-        (d === -1 && Math.floor(empty / 3) !== Math.floor(target / 3))
+        target < 0 || target >= TILE_COUNT ||
+        (d === 1 && Math.floor(empty / SIZE) !== Math.floor(target / SIZE)) ||
+        (d === -1 && Math.floor(empty / SIZE) !== Math.floor(target / SIZE))
       ) continue;
       const newState = state.slice();
       [newState[empty], newState[target]] = [newState[target], newState[empty]];
```
</details>

---

### 実施内容
- 3×3のスライドパズル実装を4×4に拡張。
- 盤面サイズ（SIZE）を変数化し、4に設定。
- CSSではパネル1つのサイズを63px×63pxに縮小（255÷4）。

```js
const SIZE = 4;
const TILE_COUNT = SIZE * SIZE;
```
- その他基本構成やA*アルゴリズムはそのまま適用。

### 発生した問題
- 探索数が爆発的に増え、**帰ってこないケースが多発**。
- 探索中にブラウザ画面（タイマー含む）**フリーズ**。
- リロード操作にも応答しないことがあった。ブラウザタブを閉じるしかなくなる。

### 理論背景
- 3×3パズルの状態数：約18万通り
- 4×4パズルの状態数：約10兆通り
- 5×5パズルの状態数：計算不能

たった1サイズの拡張（3→4）でも、探索空間は**天文学的に増加**するため、  
既存のA*アルゴリズムでは到底現実的な探索はできなくなった。
状態数が何千倍〜何万倍になっていて、
1手1手違うだけで、指数的に候補が増えていきます。
仮に1秒間に1億探索できても、全探索は数年かかるレベル。
参考までに、サイズ５は無理っぽい。＃やろうとしてました。

| 盤面サイズ | 状態数 | パズル的にあり得る状態数 |
|:-----|:--|:----|
| 3 | 9!、約36万2千通り | 半分の約18万通り |
| 4 | 16!、約20兆通り | 半分の約10兆通り |

→何故半分？
パズルの初期状態と目標状態の **転倒数（inversion number）** の偶奇性が一致している必要がある。
もし一致していなければ、どれだけ操作しても目標状態にたどり着くことはできない。
これにより、約半分の状態が探索対象から除外される。
ルール破ってピースを外して入れ替える、ということはしない、できない、考えない、ということ。

---

<details><summary>転倒数について</summary>

# 理論的な最大状態数の約半分が到達不可能になる理由：転倒数（Inversion Number）

スライドパズルの到達可能性は、**転倒数（Inversion Number）** という概念で説明できます。

転倒数とは: ある盤面において、空白を除いたピースの順番を見たときに、数字の大きいピースが数字の小さいピースよりも左（または上）に現れるペアの数のことです。
例えば、以下の3x3の盤面を考えます（空白を9で表します）。

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

この盤面の転倒数を数えます。

- (8, 7) のペアで1つ

したがって、この盤面の転倒数は1です。

スライドパズルの重要な性質として、1回のスライド操作（上下左右にピースを動かして空白と入れ替える操作）を行うと、盤面の転倒数の偶奇性は必ず変化します。

- 空白が横方向に移動する場合、転倒数は変化しません。
- 空白が縦方向に移動する場合、飛び越えるピースの数だけ転倒数の偶奇性が変化します。

さて、目標状態（例えば、以下のような昇順に並んだ状態）の転倒数は0（偶数）です。

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

初期状態の転倒数が偶数であれば、偶数回の操作で目標状態に到達できる可能性があります。
一方、初期状態の転倒数が奇数であれば、奇数回の操作で目標状態に到達できる可能性があります。

# 重要な点:

- 初期状態の転倒数が偶数の場合、転倒数が奇数の状態には決して到達できません。
- 初期状態の転倒数が奇数の場合、転倒数が偶数の状態には決して到達できません。

全ての盤面の配置を考えると、その約半分は転倒数が偶数、残りの約半分は転倒数が奇数になります。
したがって、特定の初期状態から到達可能な状態は、全ての理論的な最大状態数の約半分に限定されるのです。

</details>

---

## ② IDA*アルゴリズム＋同期処理版（v401→v402）

<details><summary>diff</summary>

```diff
diff -u v401_script.js v402_script.js
--- v401_script.js      2025-04-27 23:00:13.093500100 +0900
+++ v402_script.js      2025-04-27 23:01:07.858020600 +0900
@@ -169,7 +169,7 @@
   }, 300);
 });

-// A*探索
+// IDA*探索
 function solvePuzzle(initialTiles) {
   const goal = [...Array(TILE_COUNT - 1).keys()].map(n => n + 1).concat(null);

@@ -204,39 +204,48 @@
     return neighbors;
   }

-  // A*メイン探索関数
-  const open = [{ state: initialTiles, path: [], cost: 0 }];
-  const visited = new Set();
-
-  while (open.length > 0) {
-    open.sort((a, b) => (a.cost + manhattan(a.state)) - (b.cost + manhattan(b.state)));
-    const current = open.shift();
-    const key = current.state.join(',');
-    if (visited.has(key)) continue;
-    visited.add(key);
-    trialCount++;
-    if (trialCount % 1000 === 0) {
-      console.log(`[HELP AI] trialCount now: ${trialCount}`);
-    }
-    if (key === goal.join(',')) {
-      console.log(`[HELP AI] trialCount: ${trialCount}`);
-      console.log(`[HELP AI] solution: ${current.path.length} sreps`);
-      return current.path;}
-
-    for (const neighbor of getNeighbors(current.state)) {
-      open.push({
-        state: neighbor.state,
-        path: [...current.path, neighbor.move],
-        cost: current.cost + 1
-      });
+  // IDA*メイン探索関数
+  let threshold = manhattan(initialTiles);
+  let solutionMoves = [];
+
+  function search(path, g) {
+    const state = path[path.length - 1];
+    const f = g + manhattan(state);
+    if (f > threshold) return f;
+    if (state.join() === goal.join()) return "FOUND";
+
+    let min = Infinity;
+    for (const neighbor of getNeighbors(state)) {
+      if (path.some(p => p.join() === neighbor.state.join())) continue;
+      const t = search([...path, neighbor.state], g + 1);
+      trialCount++;
+      if (trialCount % 1000 === 0) {
+        console.log(`[HELP AI] trialCount now: ${trialCount}`);
+      }
+      if (t === "FOUND") {
+        solutionMoves.push(neighbor.move);
+        return "FOUND";
+      }
+      if (t < min) min = t;
     }
+    return min;
+  }
+
+  // 閾値を増やしながら反復深化
+  while (true) {
+    const t = search([initialTiles], 0);
+    if (t === "FOUND") break;
+    if (t === Infinity) return [];
+    threshold = t;
   }
-  return [];
+  return solutionMoves.reverse();
 }

 // AIによる自動解答実行
 function autoSolve() {
   const solution = solvePuzzle(tiles);
+  console.log(`[HELP AI] trialCount: ${trialCount}`);
+  console.log('[HELP AI] solution steps:', solution.length);
   console.log('[HELP AI] solution:', solution);

   let index = 0;
@@ -250,6 +259,7 @@
     moveTile(solution[index]);
     index++;
   }, 300);
+  console.log(`[HELP AI] trial end at: ${timerLabel.textContent}`);
 }

 // HELPボタン押下時にAI起動
```

</details>

---

### 実施内容
- アルゴリズムを`A*`から`IDA*`（Iterative Deepening A*）に変更。
- f=g+hでしきい値（threshold）を設け、段階的に深さ優先探索する構成に。
- メモリ使用を最小限に抑え、完了判定は段階的に行う。

```js
while (true) {
  const t = search([initialTiles], 0);
  if (t === "FOUND") break;
  if (t === Infinity) return [];
  threshold = t;
}
```

- solvePuzzle()関数をIDA*版に刷新。

### 改善できた点
- 状態によっては**現実的な時間（数十秒から数分程度）で解答が得られる**ようになった。

### 理論背景（`A*`と`IDA*`の違い）
| 特徴 | A* | IDA* |
|:-----|:--|:----|
| 探索方法 | open/visitedをキュー管理（幅優先＋ヒューリスティック） | 深さ優先＋段階的制限 |
| メモリ使用 | 非常に多い（全候補保持） | 少ない（pathのみ保持） |
| 速度 | 小規模なら高速 | 大規模ならIDA*有利 |

- 次はタイマーなどの画面更新も可能にしようとする。

---

## ③ IDA*アルゴリズム＋非同期処理版（v402→v403）

<details><summary>diff</summary>

```diff
diff -u v402_script.js v403_script.js
--- v402_script.js      2025-04-27 23:01:07.858020600 +0900
+++ v403_script.js      2025-04-27 23:01:30.088150300 +0900
@@ -169,8 +169,8 @@
   }, 300);
 });

-// IDA*探索
-function solvePuzzle(initialTiles) {
+// 非同期でIDA*探索
+async function solvePuzzleAsync(initialTiles) {
   const goal = [...Array(TILE_COUNT - 1).keys()].map(n => n + 1).concat(null);

   // マンハッタン距離の計算
@@ -208,20 +208,24 @@
   let threshold = manhattan(initialTiles);
   let solutionMoves = [];

-  function search(path, g) {
+  async function search(path, g) {
     const state = path[path.length - 1];
     const f = g + manhattan(state);
     if (f > threshold) return f;
     if (state.join() === goal.join()) return "FOUND";

     let min = Infinity;
-    for (const neighbor of getNeighbors(state)) {
+    const neighbors = getNeighbors(state);
+
+    for (const neighbor of neighbors) {
       if (path.some(p => p.join() === neighbor.state.join())) continue;
-      const t = search([...path, neighbor.state], g + 1);
+      await new Promise(resolve => setTimeout(resolve, 0));
       trialCount++;
       if (trialCount % 1000 === 0) {
+        helpBtn.textContent = `trial ${trialCount.toLocaleString()}`;
         console.log(`[HELP AI] trialCount now: ${trialCount}`);
       }
+      const t = await search([...path, neighbor.state], g + 1);
       if (t === "FOUND") {
         solutionMoves.push(neighbor.move);
         return "FOUND";
@@ -233,7 +237,7 @@

   // 閾値を増やしながら反復深化
   while (true) {
-    const t = search([initialTiles], 0);
+    const t = await search([initialTiles], 0);
     if (t === "FOUND") break;
     if (t === Infinity) return [];
     threshold = t;
@@ -242,11 +246,13 @@
 }

 // AIによる自動解答実行
-function autoSolve() {
-  const solution = solvePuzzle(tiles);
+async function autoSolve() {
+  const solution = await solvePuzzleAsync(tiles);
+  helpBtn.disabled = false;
+  helpBtn.textContent = `trial ${trialCount.toLocaleString()}`;
+  helpBtn.disabled = true;
   console.log(`[HELP AI] trialCount: ${trialCount}`);
-  console.log('[HELP AI] solution steps:', solution.length);
-  console.log('[HELP AI] solution:', solution);
+  console.log(`[HELP AI] trial end at: ${timerLabel.textContent}`);

   let index = 0;
   const interval = setInterval(() => {
@@ -259,7 +265,6 @@
     moveTile(solution[index]);
     index++;
   }, 300);
-  console.log(`[HELP AI] trial end at: ${timerLabel.textContent}`);
 }

 // HELPボタン押下時にAI起動
```

</details>

---

### 実施内容
- solvePuzzle()を非同期版 solvePuzzleAsync()に置き換え。
- 各ノード探索ごとにawaitを挟み、タイマー・ラベル更新を可能にした。

```js
  await new Promise(resolve => setTimeout(resolve, 0));
```

- HELPボタンの表示もtrialCountに応じて更新。

### 改善できた点
- **探索中もタイマーが動き続ける**ようになった。
- **探索試行回数もリアルタイムで表示**できるようになった。

### 新たに発生した問題
- 1手ごとにawaitしていたため、**探索速度が極端に劣化**。
- 数万試行を超えると探索時間が数分以上かかり、事実上実用に耐えなくなった。

### 理論背景
- awaitはタスクキューに戻るため、1回ごと数msのオーバーヘッドが発生。
- 毎手数msの遅延×数十万手＝数分レベルの遅延。

---

## ④ IDA*アルゴリズム＋非同期バッチ処理版（v403→v404）

<details><summary>diff</summary>

```diff
diff -u v403_script.js v404_script.js
--- v403_script.js      2025-04-27 23:01:30.088150300 +0900
+++ v404_script.js      2025-04-27 23:02:41.177837500 +0900
@@ -207,6 +207,7 @@
   // IDA*メイン探索関数
   let threshold = manhattan(initialTiles);
   let solutionMoves = [];
+  let batchCounter = 0;

   async function search(path, g) {
     const state = path[path.length - 1];
@@ -219,12 +220,20 @@

     for (const neighbor of neighbors) {
       if (path.some(p => p.join() === neighbor.state.join())) continue;
-      await new Promise(resolve => setTimeout(resolve, 0));
+
       trialCount++;
-      if (trialCount % 1000 === 0) {
+      batchCounter++;
+
+      if (trialCount % 10000 === 0) {
         helpBtn.textContent = `trial ${trialCount.toLocaleString()}`;
         console.log(`[HELP AI] trialCount now: ${trialCount}`);
       }
+
+      if (batchCounter >= 100) {
+        await new Promise(resolve => setTimeout(resolve, 0));
+        batchCounter = 0;
+      }
+
       const t = await search([...path, neighbor.state], g + 1);
       if (t === "FOUND") {
         solutionMoves.push(neighbor.move);
```

</details>

---

### 実施内容
- 非同期探索中、一定回数(batchCounter)ごとにだけawaitする設計に改善。
- バッチ単位設定：**100手探索ごとにawait 1回**

```js
if (batchCounter >= 100) {
  await new Promise(resolve => setTimeout(resolve, 0));
  batchCounter = 0;
}
```

- HELPボタンは引き続きtrialCountに応じてリアルタイム更新。
- タイマーも問題なく更新。

### 改善できた点
- **探索速度が同期版とほぼ同等レベルに復帰**。
- **タイマーもHELPラベルも滑らかに進行**。
- 数十万試行クラスの探索でも**実用的な数十秒以内で完了可能**になった。

### バッチ処理単位「100」の根拠
- 仮に1試行1msかかると仮定しても、100ms単位で一度息継ぎできる。
- 100ms間隔なら人間が「止まってる」と感じないレベル。
- 描画更新と探索速度とのバランスが良いはず。

→4/29　1000にしても大丈夫そうだし高速化できたので修正しました。

---

# 変遷まとめ

| バージョン | 更新内容 | 問題点 | 改善点 |
|:----------|:-----|:-------|:------|
| v301→v401 | 3×3→4×4へ拡張、A*同期探索 | 帰ってこない、タイマー停止 | - |
| v401→v402 | IDA*導入 | タイマー停止 | 現実的な時間で完了 |
| v402→v403 | 非同期化（毎手await） | 遅すぎる | タイマー動作OK |
| v403→v404 | 非同期＋バッチ処理 | - | 速度・描画両立達成 |

---

<details><summary>thresholdについて</summary>

# 「しきい値（threshold）」の仕組み

## そもそも「しきい値（threshold）」とは？

- IDA*では、「今探索していいノードの最大評価値(f=g+h)」を制限する。
- この制限値を「しきい値（threshold）」と呼ぶ。
- 今回の実装では初回は「スタート状態のマンハッタン距離」で決める。
  - つまり「今の位置からゴールまで、ざっくりこのくらいコストがかかりそう」という見積もり。
- これにより、無駄な深い探索を抑えながら、現実的な範囲内で探索を進める。

---

## 具体的な流れ

まず、初期しきい値を設定する。

```js
let threshold = manhattan(initialTiles);
```

ここでの `manhattan(initialTiles)` は、  
スタート地点からゴールまでのマンハッタン距離（最も単純な推定コスト）を計算する。

例：スタート状態のマンハッタン距離が「12」なら、しきい値は「12」から開始。

---

次に、探索を開始するメインループ。

```js
while (true) {
  const t = await search([initialTiles], 0);
  if (t === "FOUND") break;
  if (t === Infinity) return []; // ゴール不能な場合
  threshold = t;
}
```

ここで重要なポイント：

- `search()`関数は、現在のしきい値以内でゴールに到達できるか探索する。
- もし、すべてのノードがしきい値を超えてしまったら、その中で**最も小さかった超過値**を`t`として返す。
- 次の探索では、その`t`を新たなしきい値とする。

つまり：

| ステップ | しきい値（threshold） | 意味 |
|:--------|:----------------------|:----|
| 最初 | スタート地点のマンハッタン距離 | 「これくらいのコストで届くなら探索してOK」 |
| 1回目探索失敗 | 次に小さい超過f値 | 「もう少し深く見よう」 |
| 2回目探索失敗 | さらに小さい超過f値 | 「さらに深く」 |
| ... | 繰り返し | |
| ゴール発見 | - | 探索終了 |

この「探索→失敗→しきい値更新→再探索」を、**何回も繰り返してゴールに近づく**のがIDA*の特徴です。

---

## 流れイメージ

    初期状態
      ↓
    マンハッタン距離計算（初期threshold決定）
      ↓
    threshold以内で深さ優先探索
      ↓
    ゴール見つからず → 最小超過f値を新thresholdに
      ↓
    threshold更新して再探索
      ↓
    ゴール発見 → 完了！

---

# これを踏まえてコードを読むと

```js
let threshold = manhattan(initialTiles);
while (true) {
  const t = await search([initialTiles], 0);
  if (t === "FOUND") break;
  if (t === Infinity) return [];
  threshold = t;
}
```

「最初は最小限の範囲だけ探索し、必要になったら段階的に探索範囲を広げていく」
という設計になっていることがわかるはず

</details>

---

<details><summary>searchについて</summary>

# solvePuzzleAsync内の search(path, g) 関数 詳細解説


## search()関数の概要

- 現在のパス（path）と累積コスト（g）を元に、
- しきい値(threshold)以内でゴールを探索する「1回の深さ優先探索」。
- ゴールを発見したら `FOUND` を返し、
- もし探索不能なら、次回以降必要なしきい値を計算する。

---

## search() 関数の中身をステップごとに解説

### ① 現在の状態（state）を取得

```js
const state = path[path.length - 1];
```

- 現在のパスの最後の状態（現在地）を取り出す。
- これを起点に、次にどこへ進むかを考える。

---

### ② f値（g + h）を計算

```js
const f = g + manhattan(state);
```

- f値 = 実際にここまで来たコスト(g) + ゴールまでの推定コスト(h)。
- マンハッタン距離（h）は「どれだけ遠いか」をざっくり見積もるための値。

---

### ③ しきい値オーバーチェック

```js
if (f > threshold) return f;
```

- f値が現在のしきい値(threshold)を超えたら、
- **ここではこれ以上探索しない**。
- 代わりに、そのf値を返して「次回探索に向けた参考情報」とする。

---

### ④ ゴール判定

```js
if (state.join() === goal.join()) return "FOUND";
```

- 現在地(state)がゴールと一致するなら、
- これ以上探索は不要、`FOUND`を即返す。

---

### ⑤ 最小超過f値を記録するために初期化

```js
let min = Infinity;
```
- 子ノードたちを探索していく中で、
- 「しきい値を超えたけど一番小さかったf値」を覚えておくための変数。

---

### ⑥ 隣接ノードを生成

```js
const neighbors = getNeighbors(state);
```

- 現在地から合法的に動けるすべての隣ノード（上下左右）をリスト化。
- これからこの隣ノードたちを順に探索していく。

---

### ⑦ 隣ノードを順番に探索

```js
for (const neighbor of neighbors) {
```

- 1つずつ隣ノードを取り出して、以下の手順を行う。

---

#### ステップ⑦-1: ループ検出・スキップ

```js
if (path.some(p => p.join() === neighbor.state.join())) continue;
```

- すでに通った状態(path)と同じなら無限ループになるのでスキップ。

---

#### ステップ⑦-2: 試行回数カウント・バッチ制御

```js
trialCount++;
batchCounter++;
```

- 試行回数をカウント。
- batchCounterも増やして、一定回数ごとにブラウザに制御を戻す準備。

```js
if (trialCount % 10000 === 0) {
  helpBtn.textContent = `trial ${trialCount.toLocaleString()}`;
}
```

- 1万試行ごとにHELPボタンのラベルを更新し、進捗を可視化。

```js
if (batchCounter >= 100) {
  await new Promise(resolve => setTimeout(resolve, 0));
  batchCounter = 0;
}
```

- 100試行ごとにawaitしてブラウザの応答性を確保。

---

#### ステップ⑦-3: 再帰的にsearch呼び出し

```js
const t = await search([...path, neighbor.state], g + 1);
```

- 隣ノードに実際に移動した場合の探索を再帰的に実行。
- コスト(g)を1増やして探索を進める。

---

#### ステップ⑦-4: ゴール発見チェック

```js
if (t === "FOUND") {
  solutionMoves.push(neighbor.move);
  return "FOUND";
}
```

- 再帰探索結果が`FOUND`なら、現在の移動手を記録しつつ`FOUND`を返す。

---

#### ステップ⑦-5: しきい値更新候補の記録

```js
if (t < min) min = t;
```

- 隣ノード探索でしきい値を超えた場合、最小の超過値を覚えておく。
- これを次回のthreshold更新に使う。

---

### ⑧ 全隣ノード探索終了後

```js
return min;
```

- 隣ノードすべて探索してもゴールが見つからなかった場合、
- 今回の探索で出た「最小超過f値」を返す。

---

## まとめ

- searchは「現在地→合法な隣ノード→さらに合法な隣ノード」とどんどん探索を深く進める。
- ゴールを見つけたらすぐに\"FOUND\"を返す。
- ゴールが見つからなかったら、次に必要なしきい値(最小超過f)を返す。
- 深く探索しつつも、定期的にawaitしてブラウザの応答性を確保している。

---

# イメージ

    [開始]
      ↓
    f値がしきい値を超えた？
       ├─ はい → f値返す
       └─ いいえ
             ↓
        ゴール到達した？
           ├─ はい → FOUND返す
           └─ いいえ
                 ↓
            隣ノード探索（再帰的にsearch呼び出し）
                 ↓
        最小超過f値を記録
                 ↓
    [全部探索し終えたら] 最小超過f値をreturn

</details>

---

# 現状到達点

- 4×4パズルも状態によっては **数十秒から数分で自動解答可能** 。
- タイマー・HELPラベル更新もリアルタイム対応。
- ブラウザ応答性も維持。

# 現状の限界
- 敢えて上半分に9以上、下半分に8以下を固めてやってみると、流石に帰ってこなくなる。
- 可能な限り、答えの感じに近くしてから助けを呼んでください。いじわるしないでください。
- 一定時間経過したら、「もうちょっと答えに近くしてから呼んでね」って感じで制御を返した方が良いかも。

## 参考記録
- Win10,chrome,CPU Xeon E3-1270v3, mem16GBで以下の結果でした。

| ver | 状態 | 試行回数 | 所要時間 | 手数 | t/s |
|:----------|:-----|-------:|:------|:------|:------|
| v401 | シャッフル直後自動解答開始 | 94,382試行 | 3822秒=1時間ちょっと | 30手 | 25 |
| v402 | 状態悪化させて自動解答開始 | 632,152,906試行 | 36988秒=10時間半くらい | 61手 | 17,091 |
| v403 | シャッフル直後自動解答開始 | 323,754試行 | 4492秒=1時間半くらい | 34手 | 72 |
| v404 | 状態悪化させて自動解答開始 | 1,021,260,000試行 | 30時間半くらいで中断 | ‐ | 9,302 |

- 詰まり、端末性能次第かもですが、どの実装もそのうち帰ってくるはず。一応ちゃんと探索は継続されている。
- 4つの探索並行させても、CPUは50％程度だったことを考えると、試行した環境ではCPUボトルネックではなさそう。
- 探索速度はやはりv402が速そう。v404の二倍くらいに見える。
- でも、10時間以上、というか3分以上待つ気にはなれないので、根本的にアルゴリズム見直すべきと思う。


4/29追記　v404計測
- Win10,chrome,CPU Core m3 8100Y,mem8GB : 4,825 t/s
- iPhoneSE2,safari,CPU A13, mem3GB : 13,000 t/s
  - iPhoneめっちゃ速い( ﾟДﾟ)

↓バッチ単位を100→1000としたら
- Win10,chrome,CPU Xeon E3-1270v3,mem16GB : 19,238 t/s
- Win10,chrome,CPU Core m3 8100Y,mem8GB : 10,545 t/s
- iPhoneSE2,safari,CPU A13, mem3GB : 48,108 t/s
  - iPhoneめっちゃ速い＼(^o^)／

---