[初心者向け] JavaScriptを使った8パズルの作り方

#はじめに
この記事では以下のような8パズルを作っていきます。
![スクリーンショット 2020-04-30 1.39.04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/601599/0849745f-4bef-bc5e-ba9e-8e7b4de75db9.png)
JavaScriptへの理解を深めたい、簡単なものを作ってみたいという方にちょうど良いのではないかと思います。
8パズルが何かわからない方は[コチラ](https://qiita.com/exrd/items/8bc0be17a15ff77d3754)を参照してください。
空白のマスに隣接しているマスをクリックするとパズルが動く仕組みになっています。
また、リセットボタンを押すことで、パズルの初期化を行うことができます。

以下にソースコードとその説明を記載しておりますので、参考にしてください。

追記：
ソースコードの書き方が古いというご指摘がありましたが、トランスパイルをする必要がないこと、実際のプログラミングスクールではES5での書き方で教えている場合があることなどを考慮し、ES5で書いた方が初心者にとって優しいのではないかと思い、あえてこの書き方をしています。
ご了承ください。
#ソースコード
今回はindex.html, style.css, app.jsの3つのファイルを使いました。htmlやcssはあまり凝ったものではないので、ご自身でお好きなようにアレンジしていただいても大丈夫です。

```html:index.html
<!DOCTYPE html>
<html lang="ja">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>puzzle</title>
    <link rel="stylesheet" href="./css/style.css">
</head>
<body>
    <div id="main">
        <div class="panel" id="js-show-panel">
        </div>
        <button class="reset" id="js-reset-puzzle">
            リセット
        </button>
    </div>
    <script src="./js/app.js"></script>  
</body>
</html>
```
```css:style.css
body {
    height: 100vh;
    display: flex;
    justify-content: center;
    align-items: center;
}
.panel {
    width: 300px;
    margin: 0 auto;
    display: flex;
    flex-wrap: wrap;
}
.tile-wrapper {
    width: 100px;
    height: 100px;
    box-sizing: border-box;
    padding-right: 3px;
    padding-bottom: 3px;
}
.tile {
    width: 100%;
    height: 100%;
    line-height: 97px;
    text-align: center;
    border: 1px solid #333;
    border-radius: 5px;
    font-size: 26px;
    cursor: pointer;
}

.tile-0 {
    background: rgb(247, 200, 200);
}
.tile-1 {
    background: rgb(254, 255, 201);
}
.tile-2 {
    background: rgb(207, 255, 195);
}
.tile-3 {
    background: rgb(200, 238, 247);
}
.tile-4 {
    background: rgb(238, 200, 247);
}
.tile-5 {
    background: rgb(200, 205, 247);
}
.tile-6 {
    background: rgb(255, 197, 164);
}
.tile-7 {
    background: rgb(135, 253, 106);
}
.tile-8 {
    background: rgb(250, 140, 226);
}
.tile-none {
    background: rgb(228, 228, 228);
}

.reset {
    margin: 0 auto;
    width: 300px;
    text-align: center;
    cursor: pointer;
    background: rgb(255, 146, 146);
    padding: 10px 0;
    border-bottom: 3px solid rgb(185, 104, 104);
    margin-top: 30px;
    font-size: 16px;
}
.reset:active {
    transform: translateY(3px);
    border: none;
}
.reset:focus {
    outline: none;
}
```
```javascript:app.js
window.onload = function() {
    // =====================================
    // 関数定義
    // =====================================
    // 初期化用関数
    function init() {
        // 空文字と1~8の数字が格納された配列を生成
        var arr = ['']
        for(i = 0; i < 8; i++) {
            arr.push((i + 1).toString());
        }
        // 生成した配列をシャッフルする
        shuffle(arr);
        // 解決可能なパズルかどうか判定する
        if(!isSolved(arr.slice(0, arr.length))) { // 解決不可能なら
            // パズルを初期化
            init();
        }else { // 解決可能なら
            // パズルを描画する
            render(arr);
        }
    }

    // 配列シャッフル用関数
    function shuffle(arr) {
        var i = arr.length;
        while(i) {
            // 0 ~ 最大8までの乱数を生成
            var j = Math.floor(Math.random() * i--);
            // 配列の要素番号がiとjに該当する箇所の値を入れ替える
            swap(i, j, arr);
        }
    }
    
    // 配列の値入れ替え用関数
    function swap(i, j, arr) {
        var tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 解決可能なパズルかを判定する関数
    function isSolved(arr) {
        // #############################
        // 本文内Bの処理
        // #############################
        // 配列内の空白の要素番号を格納
        var blank_index = arr.indexOf('');
        // 縦の距離の計算
        dist_vertical = Math.floor(((arr.length - 1) - blank_index) / Math.sqrt(arr.length));
        // 横の距離の計算
        dist_horizontal = ((arr.length - 1) - blank_index) % Math.sqrt(arr.length);
        // 縦と横を足し合わせる
        var dist = dist_vertical + dist_horizontal;

        // #############################
        // 本文内Aの処理
        // #############################
        // 答えの配列を生成
        answer = [];
        for(i = 0; i < 8; i++) {
            answer.push((i + 1).toString());
        }
        answer.push('');

        // 入れ替えが起きた回数を記録する
        var count = 0;
        // パズルを答えの形に並び替える
        for (var i = 0; i < answer.length; i++) {
            for (var j = i + 1; j < answer.length; j++) {
                // 要素番号＋1の数が格納されている箇所と入れ替える
                if(i + 1 == arr[j]) { 
                    swap(i, j, arr);
                    // 入れ替えが起きたら1プラスする
                    count++;
                }
            }
            // 答えの配列と同じになったかどうかを判定
            if(arr.toString() === answer.toString()) {
                // 同じならばループから抜ける
                break;
            }
        }

        // 判定処理
        if(count % 2 === dist % 2) { // 解決可能なパズルなら
            return true;
        }else { // 解決不可能なパズルなら
            return false;
        }
    }

    // パズル描画用関数
    function render(arr) {
        var $jsShowPanel = document.getElementById('js-show-panel');
        // すでにパズルが描画されていたら、それらを一旦削除する
        while($jsShowPanel.firstChild) {
            $jsShowPanel.removeChild($jsShowPanel.firstChild);
        }
        
        // フラグメント生成
        fragment = document.createDocumentFragment();
        // 描画用のHTML生成
        arr.forEach(function(element) {   
            var tileWrapper = document.createElement('div');
            tileWrapper.className = 'tile-wrapper';
    
            var tile = document.createElement('div');
            tile.className = element != '' ? 'tile tile-' + element : 'tile tile-none';
            tile.textContent = element;

            tileWrapper.appendChild(tile);
            fragment.appendChild(tileWrapper);
        });
        // 描画
        $jsShowPanel.appendChild(fragment);
        // クリックイベントを追加
        addEventListenerClick(arr);
    }

    // パズルをクリックイベント追加用関数
    function addEventListenerClick(arr) {
        // クラス名にtileがつくDOM一つ一つにクリックイベントを追加
        $tile = document.querySelectorAll('.tile');
        $tile.forEach(function(elem) {
            elem.addEventListener('click', function() {
                // 引数に渡された配列（パズルの並びを表す）においてクリックされた数字が格納されている要素番号を変数に代入
                var i =  arr.indexOf(this.textContent);
                // クリックされたパズルの移動先を格納する変数
                var j;
                // クリックされたパズルが上2行かつクリックされたパズルの下のマスが空白だったら
                if(i <= 5 && arr[i + 3] == '') {
                    // 下方向へ移動
                    j = i + 3;
                }
                // クリックされたパズルが下2行かつクリックされたパズルの上のマスが空白だったら
                else if(i >= 3 && arr[i - 3] == '') {
                    // 上方向へ移動
                    j = i - 3;
                    
                }
                // クリックされたパズルが左2列かつクリックされたパズルの右のマスが空白だったら
                else if(i % 3 != 2 && arr[i + 1] == '') {
                    // 右方向へ移動
                    j = i + 1;
                // クリックされたパズルが右2列かつクリックされたパズルの左のマスが空白だったら
                }else if(i % 3 != 0 && arr[i - 1] == '') {
                    // 左方向へ移動
                    j = i - 1;
                }
                // クリックされたパズルが移動させられなかったら
                else {
                    // なにもしない
                    return;
                }
                // パズルを移動
                swap(i, j, arr);
                // パズルを再描画
                render(arr);
            });
        });
    }

    // =====================================
    // メイン処理
    // =====================================
    // パズルの初期化
    init();
    // パズルのリセット
    document.getElementById('js-reset-puzzle').addEventListener('click', function() {
        init();
    });
}
```
#ソースコード解説
## 初期化
```javascript
// 初期化用関数
    function init() {
        // 空文字と1~8の数字が格納された配列を生成
        var arr = ['']
        for(i = 0; i < 8; i++) {
            arr.push((i + 1).toString());
        }
        // 生成した配列をシャッフルする
        shuffle(arr);
        // パズルを描画する
        render(arr);
    };
```
パズルを最初に画面に描画するための処理が記述された関数です。
まず、空文字と1~8までが格納されている配列[arr]を作ります。
配列の作り方は、色々あると思いますが今回は空文字が格納されている配列を作り、そこにfor文で1~8の数字を入れていくという方法で行いました。
配列をつくったあとは、パズルがランダムで表示されるようにシャッフル用関数を使って配列をシャッフルします。
その後、解決可能なパズルかどうかを判定し、解決可能なパズルであれば画面描画用関数をつかって配列をパズルとして画面に描画します。反対に解決不可能なパズルであればもう一度パズルの初期化を行います。
## シャッフル
```javascript
    // 配列シャッフル用関数
    function shuffle(arr) {
        var i = arr.length;
        while(i) {
            // 0 ~ 最大8までの乱数を生成
            var j = Math.floor(Math.random() * i--);
            // 配列の要素番号がiとjに該当する箇所の値を入れ替える
            swap(i, j, arr);
        }
    }
```
引数で渡された配列の中身をシャッフルする関数です。
まず、引数で渡された配列の長さ（今回は9）を変数に代入します。
そして、その変数の値が0になるまで処理を繰り返すことで配列をシャッフルします。
その繰り返す処理の内容ですが、

```javascript
var j = Math.floor(Math.random() * i--);
```
この部分で0~最大8までの整数を生成します。
最大8までとはどういうことかというと、Math.random()で生成した0以上1未満の乱数に整数i(初期値は9)をかけたものをMath.floor()で切り捨て整数化しています。ですので、最大で8までの整数が生成されるんですね。ただ、毎回のループのなかで整数iは1ずつ小さくなっていきますので、生成される整数の範囲はどんどん小さくなっていきます。
整数が生成できたら、各ループにおける整数iと整数jを使って配列をスワップ（配列の中身の順番をいれかえること）します。
## スワップ
```javascript
    // 配列の値入れ替え用関数
    function swap(i, j, arr) {
        var tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
```
配列の中身の順番をい入れ替えるスワップを行う関数です。
引数には入れ替えを行う要素の番号と、入れ替えを行う配列を渡します。
まず、tmpという変数に配列のi番目の要素の値を入れて、記憶しておきます。
そして、そのi番目の要素の値を入れ替え先のj番目の要素の値に変更します。
最後に、j番目の要素の値をはじめにtmpに記憶しておいた値に変更します。
これで、2つの値の入れ替えができました。
## 解決可能なパズルかどうか判定（追記：2020/07/13）
コメントで単純に配列をシャッフルすると、絶対に[1, 2, 3, ・・・, 8, 空白]の順に並び替えられることのできない解決不可能なパズルが生成されるというご指摘をいただきました。
そこで、解決可能なパズルかどうかを判定するためのプログラムを追加しました。
### 判定方法
```javascript
// 解決可能なパズルかを判定する関数
    function isSolved(arr) {
        // #############################
        // 本文内Bの処理
        // #############################
        // 配列内の空白の要素番号を格納
        var blank_index = arr.indexOf('');
        // 縦の距離の計算
        dist_vertical = Math.floor(((arr.length - 1) - blank_index) / Math.sqrt(arr.length));
        // 横の距離の計算
        dist_horizontal = ((arr.length - 1) - blank_index) % Math.sqrt(arr.length);
        // 縦と横を足し合わせる
        var dist = dist_vertical + dist_horizontal;

        // #############################
        // 本文内Aの処理
        // #############################
        // 答えの配列を生成
        answer = [];
        for(i = 0; i < 8; i++) {
            answer.push((i + 1).toString());
        }
        answer.push('');

        // 入れ替えが起きた回数を記録する
        var count = 0;
        // パズルを答えの形に並び替える
        for (var i = 0; i < answer.length; i++) {
            for (var j = i + 1; j < answer.length; j++) {
                // 要素番号＋1の数が格納されている箇所と入れ替える
                if(i + 1 == arr[j]) { 
                    swap(i, j, arr);
                    // 入れ替えが起きたら1プラスする
                    count++;
                }
            }
            // 答えの配列と同じになったかどうかを判定
            if(arr.toString() === answer.toString()) {
                // 同じならばループから抜ける
                break;
            }
        }

        // 判定処理
        if(count % 2 === dist % 2) { // 解決可能なパズルなら
            return true;
        }else { // 解決不可能なパズルなら
            return false;
        }
    }
```
判定方法は[コチラ](https://mathtrain.jp/8puzzle)に詳しく載っていますが、要は

>A. 与えられた配列で2要素の入れ替えを行い、答えの配列[1, 2, 3, ・・・, 8, 空白]になるまでに入れ替えた回数をカウント
B. 与えられたパズルで空きブロック(空白)が、最終的な到達地点(= パズルの右下)から、何マス離れているかをカウント

の二つを行うことです。そしてAとBの結果の偶奇が一致しているときに解決可能なパズルとなります。

プログラム内のAの処理では、for文を二重にネストすることで、上記したような配列の要素の入れ替えを行っています。
例えばi=0のときは正解のパズルの左上にくる値(= 1)を配列内から探し出し、入れ替えを行います。これを答えの配列[1, 2, 3, ・・・, 8, 空白]になるまで繰り返します。
また、入れ替えが起きたときは変数countを＋1することで全部で何回の入れ替えが起きたかをカウントしておきます。

プログラム内のBの処理では与えられたパズルで空きブロック(空白)が、最終的な到達地点(= パズルの右下)から、何マス離れているかを計算しています。
ただ、計算する際には実際のパズルに置き換えて考えないといけないので、配列の空きブロック（空白）の要素番号と配列末尾の要素番号の差をとってしまうと正しい距離の算出ができません。そこで、以下のように計算を行います。

`((配列の要素数 - 1) - 空白の要素番号) / パズルの1辺の距離(= 3)`

上式の**商**が縦の距離に、**余り**が横の距離に等しくなります。
そして縦と横の距離を足し合わせることで空白がパズルの右下からどれだけ離れているかを算出できます。

最後にAとBでも求めた回数と距離の偶奇が等しいかを判定しています。
## パズルの描画
```javascript
    // パズル描画用関数
    function render(arr) {
        var $jsShowPanel = document.getElementById('js-show-panel');
        // すでにパズルが描画されていたら、それらを一旦削除する
        while($jsShowPanel.firstChild) {
            $jsShowPanel.removeChild($jsShowPanel.firstChild);
        }
        
        // フラグメント生成
        fragment = document.createDocumentFragment();
        // 描画用のHTML生成
        arr.forEach(function(element) {   
            var tileWrapper = document.createElement('div');
            tileWrapper.className = 'tile-wrapper';
    
            var tile = document.createElement('div');
            tile.className = element != '' ? 'tile tile-' + element : 'tile tile-none';
            tile.textContent = element;

            tileWrapper.appendChild(tile);
            fragment.appendChild(tileWrapper);
        });
        // 描画
        $jsShowPanel.appendChild(fragment);
        // クリックイベントを追加
        addEventListenerClick(arr);
    }
```
パズルを描画する際につかう関数です。
引数に渡された配列（パズルの並びを表す）をもとに描画を行います。
ここはかなり処理が複雑ですので、初心者の方はなんとなく理解できればいいと思います。
まず、引数に渡された配列を元にループを回します。
そして、各ループでは以下のようなHTML（数字の部分は毎回変わる）を生成します。

```html
    <div class="tile-wrapper">
        <div class="tile tile-1">
            1
        </div>
    </div>
```
また、空白のマスの場合は以下のようなHTML（クラス名などが変わる）が生成されるようにしています。

```html
    <div class="tile-wrapper">
        <div class="tile tile-none">
        </div>
    </div>
```

これらのHTMLをループが終わった後に親となるDOM（上のHTMLを囲むdivタグ）に追加することで画面に描画しています。
そして、生成したDOMにクリックイベントを付与して終了です。

## パズルの移動
```javascript
// パズルをクリックイベント追加用関数
    function addEventListenerClick(arr) {
        // クラス名にtileがつくDOM一つ一つにクリックイベントを追加
        $tile = document.querySelectorAll('.tile');
        $tile.forEach(function(elem) {
            elem.addEventListener('click', function() {
                // 引数に渡された配列（パズルの並びを表す）においてクリックされた数字が格納されている要素番号を変数に代入
                var i =  arr.indexOf(this.textContent);
                // クリックされたパズルの移動先を格納する変数
                var j;
                // クリックされたパズルが上2行かつクリックされたパズルの下のマスが空白だったら
                if(i <= 5 && arr[i + 3] == '') {
                    // 下方向へ移動
                    j = i + 3;
                }
                // クリックされたパズルが下2行かつクリックされたパズルの上のマスが空白だったら
                else if(i >= 3 && arr[i - 3] == '') {
                    // 上方向へ移動
                    j = i - 3;
                    
                }
                // クリックされたパズルが左2列かつクリックされたパズルの右のマスが空白だったら
                else if(i % 3 != 2 && arr[i + 1] == '') {
                    // 右方向へ移動
                    j = i + 1;
                // クリックされたパズルが右2列かつクリックされたパズルの左のマスが空白だったら
                }else if(i % 3 != 0 && arr[i - 1] == '') {
                    // 左方向へ移動
                    j = i - 1;
                }
                // クリックされたパズルが移動させられなかったら
                else {
                    // なにもしない
                    return;
                }
                // パズルを移動
                swap(i, j, arr);
                // パズルを再描画
                render(arr);
            });
        });
    }
```
パズルをクリックした際の移動を行う関数です。
まず、パズルのDOMを全て取得します。
その後、それらのDOM全てに対してクリックしたときに動作するようにクリックイベントを追加します。
これに関してはソースコードのコメントにかなり詳しく書いてあるので、詳細は省きますが、主に4つの処理に分けられます。

1. 下2行のパズルがクリックされ、かつ、クリックされたパズルの上のマスが空白のとき（パズルを上に移動させる時）
2. 上2行のパズルがクリックされ、かつ、クリックされたパズルの下のマスが空白のとき（パズルを下に移動させる時）
3. 左2行のパズルがクリックされ、かつ、クリックされたパズルの右のマスが空白のとき（パズルを右に移動させる時）
4. 右2行のパズルがクリックされ、かつ、クリックされたパズルの左のマスが空白のとき（パズルを左に移動させる時）

これらのうちどれか一つの処理を行うことで、入れ替える先の要素番号を決定します。
そして、配列の中身の順番の入れ替え、パズルの再描画を行います。

## メイン処理
```javascript
    // =====================================
    // メイン処理
    // =====================================
    // パズルの初期化
    init();
    // パズルのリセット
    document.getElementById('js-reset-puzzle').addEventListener('click', function() {
        init();
    });
```
いままで説明してきたものはすべて関数で、メインの処理はここからになります。とはいっても、初期化用の関数しか動いていないんですが...

```javascript
    // パズルの初期化
    init();
```
初期描画のための初期化を行っています。

```javascript
    // パズルのリセット
    document.getElementById('js-reset-puzzle').addEventListener('click', function() {
        init();
    });
```
こちらはリセットボタンが押された際のリセット処理です。
中身はただ単に初期化を行っているだけです。

#まとめ
今回はJavaScriptを使った8パズルの作り方を解説しました。
ソースコードを見ながらで構いませんので、自分の手を動かして作ることで、JavaScriptのDOMの生成、配列の処理、イベントの付与などへの理解が深まるのではないかと思います。
学ぶは真似ぶ。ソースコードを参考にどんどん真似しちゃってください！