前回は複数色のライツアウトのパズルゲームを作りましたが、今回はその解を表示するライツアウトシミュレーターをつくります。2色から6色まで対応可能です。
HTML部分
HTML部分を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>Lights out simulator</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> <link rel="stylesheet" href="./style.css"> </head> <body> <div id= "container"> <div id= "container-inner"> <h1>Lights out simulator</h1> <p>Lights out の解を求めるシミュレーターです。</p> <input type="radio" id="two" name="color-count" value="two" checked> <label for="two">2 色</label> <input type="radio" id="three" name="color-count" value="three"> <label for="three">3 色</label> <input type="radio" id="four" name="color-count" value="four"> <label for="four">4 色</label> <input type="radio" id="five" name="color-count" value="five"> <label for="five">5 色</label> <input type="radio" id="six" name="color-count" value="six"> <label for="six">6 色</label> <div id= "navi">問題を入力してボタンをクリックするとそれぞれのセルをクリックする回数が表示されます。</div> <div id= "field"> </div> <button id = "calc" class = "button">解を調べる</button> <button id = "clear" class = "button">クリア</button> <div id = "volume"> 音量：<input type="range" id = "volume-range"><span id = "volume-text">0</span> <button id = "volume-test">テスト</button> </div> </div><!--/#container-inner --> </div><!--/#container --> <script src = "./index.js"></script> </body> </html> |
style.css
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
body { background-color: #000; color: #fff; } h1 { font-size: 24px; } #container { width: 360px; } #container-inner { margin-top: 20px; margin-left: 20px; } #navi { margin-top: 20px; } #field { margin-top: 20px; margin-bottom: 20px; } #volume { margin-top: 20px; } #volume-range { width: 200px; vertical-align: middle; margin-left: 10px; margin-right: 10px; } #volume-test { width: 100px; height: 50px; margin-left: 10px; margin-top: 10px; } .cell { border: 1px solid #fff; vertical-align: middle; } .button { width: 120px; height: 60px; } |
グローバル変数と定数
グローバル変数と定数を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
const ROW_COUNT = 5; // セルは 5 x 5 とする const COL_COUNT = 5; const CELL_WIDTH = 60; // セルの表示サイズ const CELL_HEIGHT = 60; // DOM要素 const $field = document.getElementById('field'); const $calc = document.getElementById('calc'); const $clear = document.getElementById('clear'); const $navi = document.getElementById('navi'); // DOM要素（ラジオボタン） const $two = document.getElementById('two'); const $three = document.getElementById('three'); const $four = document.getElementById('four'); const $five = document.getElementById('five'); const $six = document.getElementById('six'); const $radios = [$two, $three, $four, $five, $six]; // DOM要素（セル） const $cells = []; let colorCount = 2; // 色数 const colors = [ // 表示色 '#000', '#f00', '#0f0', '#0ff', '#800', '#080', '#088', ] let cellStates = []; // 各セルの状態（何回クリックされたか？） let answer = null; // クリアするためには各セルは何回クリックする必要があるか？ // 効果音 const clickSound = new Audio('./sounds/click.mp3'); const badSound = new Audio('./sounds/bad.mp3'); // 初期のボリューム let volume = 0.1; |
ページが読み込まれたときの処理
ページが読み込まれたときの処理を示します。ページが読み込まれたらセルを生成して最初はどのセルもクリック数は 0 なのでそのような情報を2次元配列 cellStates に格納します。そのあとセルへの着色、イベントリスナの追加、ボリューム設定の初期化の処理をおこないます。
|
1 2 3 4 5 6 7 8 9 |
window.onload = () => { createCells(); // セルを生成（後述） initCellStates(); // 2次元配列 cellStates の初期化（後述） setCellColors1(); // セルへの着色（後述） addEventListeners(); // イベントリスナの追加（後述） initVolume(); // ボリューム設定（後述） } |
セルを生成する
セルを生成する処理を示します。これは前回のものと同じです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
function createCells(){ for(let row = 0; row < ROW_COUNT; row++){ const $row = document.createElement('div'); $field?.appendChild($row); $cells.push([]); for(let col = 0; col < COL_COUNT; col++){ const $cell = document.createElement('div'); $cell.style.width = CELL_WIDTH + 'px'; $cell.style.height = CELL_HEIGHT + 'px'; $cell.style.marginRight = col != COL_COUNT - 1 ? 5 + 'px' : '0px'; $cell.style.marginBottom = row != ROW_COUNT - 1 ? 5 + 'px' : '0px'; $cell.style.lineHeight = CELL_HEIGHT + 'px'; $cell.style.textAlign = 'center'; $cell.style.fontSize = '32px'; $cell.innerHTML =''; $cell.className = 'cell'; $cell.id = `cell-${row}-${col}`; $cell.style.display = 'inline-block'; $cell.style.userSelect = 'none'; // クリックしても文字選択されない $row?.appendChild($cell); $cells[row].push($cell); } } } |
セルが何回クリックされたか（ただし総クリック数ではなく colorCount で割ったときの剰余）を格納する2次元配列 cellStates を初期化する処理を示します。
|
1 2 3 4 5 6 7 8 |
function initCellStates(){ cellStates = []; for(let row = 0; row < $cells.length; row++){ cellStates.push([]); for(let col = 0; col < $cells[row].length; col++) cellStates[row].push(0); } } |
2次元配列 cellStates に格納されている値をセルの色に反映させる処理を示します。setCellColors1関数はユーザーが問題を入力するためにセルをクリックしたときにも呼び出されます（解が表示されたとき以降にクリックされたときは別の処理をおこなう）。
|
1 2 3 4 5 6 7 8 9 |
function setCellColors1(){ for(let row = 0; row < $cells.length; row++){ for(let col = 0; col < $cells[row].length; col++){ const num = cellStates[row][col]; $cells[row][col].style.backgroundColor = colors[num]; $cells[row][col].innerText = num; } } } |
ボリュームをレンジスライダーで調整できるようにする処理と効果音再生の処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
function initVolume(){ const $volumeRange = document.getElementById('volume-range'); const $volumeText = document.getElementById('volume-text'); $volumeRange?.addEventListener('input', () => { const value = $volumeRange.value; $volumeText.innerText = value; volume = value / 100; setVolume(); }); setVolume(); $volumeText.innerText = volume * 100; $volumeRange.value = volume * 100; function setVolume(){ clickSound.volume = volume; badSound.volume = volume; } const $volumeTest = document.getElementById('volume-test'); $volumeTest?.addEventListener('click', () => playClickSound()); } |
|
1 2 3 4 5 6 7 8 |
function playClickSound(){ clickSound.currentTime = 0; clickSound.play(); } function playBadSound(){ badSound.currentTime = 0; badSound.play(); } |
イベントリスナの追加
セルや求解ボタン、クリアボタンがクリックされたとき、ラジオボタンの状態が変更されたときに対応するイベントリスナを追加する処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function addEventListeners(){ for(let row = 0; row < $cells.length; row++){ for(let col = 0; col < $cells[row].length; col++) $cells[row][col].addEventListener('click', () => onClickCell(row, col)); } // onClickCell, onChangeColorCount, calc, allClear 関数は後述 $calc?.addEventListener('click', () => calc()); $clear?.addEventListener('click', () => allClear()); $two?.addEventListener('change', () => onChangeColorCount(2)); $three?.addEventListener('change', () => onChangeColorCount(3)); $four?.addEventListener('change', () => onChangeColorCount(4)); $five?.addEventListener('change', () => onChangeColorCount(5)); $six?.addEventListener('change', () => onChangeColorCount(6)); } |
ラジオボタンの状態が変更されたときにおこなわれる処理を示します。
選択されたラジオボタンに合わせて colorCount の値を変更するのですが、cellStates に格納されている値のなかに colorCount – 1 より大きな値が格納されていると誤作動がおきるので、cellStates に格納されている値が colorCount – 1 を超えないように調整しています。そのあとセルの色を再設定しています。
|
1 2 3 4 5 6 7 8 |
function onChangeColorCount(value){ colorCount = value; for(let row = 0; row < cellStates.length; row++){ for(let col = 0; col < cellStates[row].length; col++) cellStates[row][col] %= colorCount; } setCellColors1(); } |
セルがクリックされたときの処理
セルがクリックされたときの処理を示します。[解を調べる]ボタンがクリックされる前はクリックされたセルだけ、解が表示されたあとはクリックされたセルとその上下左右のセルの色が変わるようにします（表示された解が本当に正しいか確認できるようにする）。両者は解が格納される2次元配列 answer が 非null であるかどうかで区別できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function onClickCell(row, col){ playClickSound(); if(answer == null){ cellStates[row][col]++; cellStates[row][col] %= colorCount; setCellColors1(); } else { answer[row][col]--; // デクリメント（格納されている値があと何回のクリックが必要かなので） if(answer[row][col] < 0) answer[row][col] += colorCount; setCellColors2(); // answer に格納されている値をセルの色に反映させる（後述） } } |
求解と結果の表示
解を求めるアルゴリズムですが、最初の1行のそれぞれのセルを何回クリックするのかが確定してしまうとそれ以降は何回クリックすべきか考えるセルの上にあるセルの色が黒になるように回数を調整するだけで解を求めることができます（要するに貪欲法）。最初の1行だけ総当たり法で全部の組み合わせを考えます。
もしこの方法ですべて黒にすることができない場合は解は存在しません。
最初の1行だけ総当たり法が必要です。そのためには 0 ～ colorCount – 1 の整数をCOL_COUNT 個組み合わせたもののすべての組み合わせ（重複順列）が必要です。これは N進法で表した 0 から n の k 乗 – 1 までの数の各桁を利用すればよいので以下のような関数を定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
function generateDuplicatePermutation(n, k){ // K桁 N進法 の整数を生成する const arrList = []; let a = Math.pow(n, k); for(let i = 0; i < a; i++){ const arr = []; for(let j = 0; j < k; j++){ const value = Math.floor((i % Math.pow(n, j + 1)) / Math.pow(n, j)); arr[k - j - 1] = value; } arrList.push(arr); } return arrList; } |
simulateOnClickCell関数は row行 col列目のセルをクリックしたら2次元配列 cellStates がどうなるかをシミュレートするためのものです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
function simulateOnClickCell(cellStates0, row, col, count){ cellStates0[row][col] += count; cellStates0[row][col] %= colorCount; const dx = [1, -1, 0, 0]; const dy = [0, 0, 1, -1]; for(let i = 0; i < 4; i++){ const nrow = row + dy[i]; const ncol = col + dx[i]; if(nrow >= 0 && ncol >= 0 && nrow < ROW_COUNT && ncol < COL_COUNT){ cellStates0[nrow][ncol] += count; cellStates0[nrow][ncol] %= colorCount; } } } |
上記の関数を用いて解を求める処理を示します。求解のアルゴリズムは上記のとおりです。cellStates のコピーを生成してこれをつかってシミュレートします。解は複数存在するのでクリック数が最小のものを求めます。
解が得られたらこれを表示し求解ボタンを非表示にするとともにラジオボタンを操作不能にします。解が存在しない場合はその旨を表示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
function calc(){ let n = colorCount; let k = COL_COUNT; const arrList = generateDuplicatePermutation(n, k); answer = null; let minClickCount = ROW_COUNT * COL_COUNT * colorCount; // 想定される最大クリックより大きな値 for(let i = 0; i < arrList.length; i++){ // cellStates のコピーを生成する let copiedCellStates = []; for(let row = 0; row < cellStates.length; row++){ const arr = []; for(let col = 0; col < cellStates[row].length; col++) arr.push(cellStates[row][col]); copiedCellStates.push(arr); } // 暫定解を格納する2次元配列を生成する let clickCounts = []; for(let row = 0; row < cellStates.length; row++){ const arr = []; for(let col = 0; col < cellStates[row].length; col++) arr.push(0); clickCounts.push(arr); } const arr = arrList[i]; let clickCount = 0; // 最初の1行は重複順列の値 for(let col = 0; col < clickCounts[0].length; col++){ simulateOnClickCell(copiedCellStates, 0, col, arr[col]); clickCounts[0][col] = arr[col]; clickCount += arr[col]; } // 2行目以降は貪欲法で for(let row = 1; row < clickCounts.length; row++){ for(let col = 0; col < clickCounts[row].length; col++){ let count = colorCount - copiedCellStates[row-1][col]; if(count == colorCount) count = 0; simulateOnClickCell(copiedCellStates, row, col, count); clickCounts[row][col] = count; clickCount += count; } } // この方法ですべてのcopiedCellStatesの要素が0になったかを調べる // できているなら解の候補、できていないのであればこの重複順列からは解は得られない let ok = true; for(let row = 0; row < clickCounts.length; row++){ for(let col = 0; col < clickCounts[row].length; col++){ let num = copiedCellStates[row][col]; if(num != 0){ ok = false; break; } } if(!ok) break; } // クリック数最小のものが最適解となる if(ok && minClickCount > clickCount){ minClickCount = clickCount; answer = clickCounts; } } // 最適解が存在する場合はセルにクリック数を表示 // 存在しない場合は解が存在しない旨を示す if(answer != null){ // 最適解が存在する場合はラジオボタンを操作不能にする for(let i = 0; i < $radios.length; i++) $radios[i].disabled = 'true'; setCellColors2(); // 後述 $navi.innerText = `これが ${colorCount} 色の最短手順 (${minClickCount}手) です。実際にクリックして確認できます。`; $calc.style.display = 'none'; playClickSound(); } else { $navi.innerText = '解は存在しません。' playBadSound(); } } |
解を取得したあとセルをクリックしたらそのセルと上下左右のセルの色を変更してクリアまでに必要なクリック数を表示させます。その処理を示します。
解が格納されている2次元配列 answer の値から各セルの色を計算することができます。そのセルに対応する answer の要素とそのセルの上下左右のセルに対応する要素の値の総和を求めます。この値を colorCount で割った剰余を求め、これを colorCount から引きます。こうして得られた値を colorCount で割った剰余が表示すべき色となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
function setCellColors2(){ for(let row = 0; row < $cells.length; row++){ for(let col = 0; col < $cells[row].length; col++){ let value = answer[row][col]; const dx = [1, -1, 0, 0]; const dy = [0, 0, 1, -1]; for(let i = 0; i < 4; i++){ const nrow = row + dy[i] const ncol = col + dx[i] if(nrow < 0 || ncol < 0 || nrow >= $cells.length || ncol >= $cells[row].length) continue; value += answer[nrow][ncol]; } let num = value % colorCount; num = colorCount - num; num %= colorCount; $cells[row][col].style.backgroundColor = colors[num]; $cells[row][col].innerText = value; } } } |
[クリア]ボタンがクリックされたときの処理を示します。
2次元配列 cellStates を初期化し、解が格納されている2次元配列 answer に null を代入して求解前の状態に戻します。またラジオボタンが操作できるようにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
function allClear(){ for(let i = 0; i < $radios.length; i++) $radios[i].disabled = ''; playClickSound(); // 求解前の状態に戻す answer = null; initCellStates(); setCellColors1(); $calc.style.display = 'inline'; $navi.innerText = '問題を入力してボタンをクリックするとそれぞれのセルをクリックする回数が表示されます。'; } |
