Fire JS Bin - solver

/*
 * Panel de Pon puzzle solver (JavaScript)
 *
 * Copyright (c) 2015 Project Nayuki
 * All rights reserved. Contact Nayuki for licensing.
 * https://www.nayuki.io/page/panel-de-pon-puzzle-solver-javascript
 */

/* User interface */

const BOARD_WIDTH = 6;
const BOARD_HEIGHT = 12;

// The 0th index is considered a blank tile. Also, this array controls how many possible tile values exist.
const TILE_COLORS = ['#000000', '#F01000', '#FFE000', '#00C000', '#40FFFF', '#0020F0', '#C000FF'];

const EXAMPLE_PUZZLES = [
  '3\n......\n......\n......\n......\n......\n...c..\n.c.c..\n.c.b..\n.b.b..\n.b.c..\n.c.b..\n.c.c..',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 01
  '3\n......\n......\n......\n......\n......\n......\n......\n......\n......\n..cf..\n..fcc.\n..cfc.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 02
  '2\n......\n......\n......\n......\n..bb..\n..ae..\n..ae..\n..bb..\n..ea..\n..ea..\nbbaebb\nbbeabb',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 03
  '3\n......\n......\n......\n......\n......\n......\n......\n......\n...a..\n...b..\n...aba\n..bbab',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 04
  '4\n......\n......\n......\n......\n......\n......\n......\n......\n......\n..de..\n..ed..\ndedede',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 05
  '3\n......\n......\n......\n......\n...a..\n...f..\n...a..\n...b..\n...a..\n...b..\n...f..\n..fb..',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 06
  '2\n......\n......\n......\n......\n......\n......\n......\n..add.\n..ebe.\n..daa.\n..edde\nb.beed',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 07
  '3\n......\n......\n......\n......\n......\n......\n......\n......\n...c..\n...dcc\n..dcdd\n..dccd',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 08
  '2\n......\n......\n......\n......\n......\n......\n...a..\n...f..\n...c..\n...c..\n..fa.a\n.ccfcf',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 09
  '3\n......\n......\n......\n......\n......\n......\n......\n......\n...e..\n.e.d..\n.ded..\n.deede',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 10
  '3\n......\n......\n......\n......\n......\n......\n......\n......\n...a..\n...fa.\n...bb.\n.bffa.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 11
  '3\n......\n......\n......\n......\n......\n......\n......\n......\n......\n..ada.\n..cdc.\n..acd.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 12
  '3\n......\n......\n......\n......\n...d..\n...b..\n...d..\n...a..\n...ab.\n...ff.\n...fb.\n...ad.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 13
  '2\n......\n......\n......\n......\n......\n......\n......\n..a...\n.ab...\n.ba...\n.bbab.\naabaa.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 14
  '3\n......\n......\n......\n......\n......\n......\n......\n......\n..aff.\n..faf.\n..bfb.\n..afb.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 15
  '3\n......\n......\n......\n......\n......\n......\n......\n......\n..b...\n.ff...\n.bff..\n.fbb..',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 16
  '2\n......\n......\n......\n......\n......\n.f....\n.a....\n.a....\n.f.a..\n.f.faa\n.a.aff\n.a.faa',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 17
  '2\n......\n......\n......\n......\n......\n..ed..\n..ed..\n..de..\n..ed..\n..de..\n..ed..\nddedee',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 18
  '4\n......\n......\n......\n......\n......\n......\n...c..\n...a..\n...c..\n...c..\n..aa..\n..cc..',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 19
  '3\n......\n......\n......\n......\n......\n......\n..a...\n..d...\n..fd..\n.afad.\nadadfd\nfafafa',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 20
  '2\n......\n......\n......\n......\n......\n...b..\n...d..\n...d..\n...b..\n...d..\n.ddbb.\n.bbdbb',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 21
  '2\n......\n......\n......\n......\n......\n......\n......\n......\n......\n.ccf..\n.ffcc.\nfccff.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 22
  '3\n......\n......\n......\n......\n......\n...c..\n...c..\n...d..\n...a..\n...ac.\n..ccdd\n..cacc',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 23
  '4\n......\n......\n......\n......\n......\n......\n......\n......\n..b...\n..e...\n.ebeb.\n.bebe.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 24
  '2\n......\n......\n......\n......\n......\n......\n......\n..a.ee\n..faff\n.aeeba\nffbbab\nbbffba',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 25
  '3\n......\n......\n......\n......\n......\n......\n......\n.c....\n.d....\n.bab..\n.cdaa.\n.dccb.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 26
  '4\n......\n......\n......\n......\n......\n......\n......\n..ad..\n..bb..\n..ad..\n..bd..\n.ada..',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 27
  '3\n......\n......\n......\n......\n......\n......\n......\n..d...\n..be..\n..bbc.\n..edd.\n..ecc.',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 28
  '3\n......\n......\n......\n......\n......\n......\n......\n.cee..\n.bff..\n.fbf..\n.ccb..\n.eff..',  // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 29
  '2\n......\n......\n......\n......\n......\n......\n...c..\n..cb..\n..ba..\n..bbc.\n..abb.\n..bab.'   // Pokémon Puzzle League - Puzzle University - Class 2 - Stage 30
];

const pageBoard = new Board(null, BOARD_WIDTH, BOARD_HEIGHT, null, null, 0);
const tbodyElem = document.getElementById('gameboard').getElementsByTagName('tbody')[0];
let currentExample = -1;

function initHtmlBoard() {
  removeChildren(tbodyElem);

// Header row
  let row = document.createElement('tr');
  row.appendChild(document.createElement('td'));
  for (let x = 0; x < pageBoard.width; x++) {
    const cell = document.createElement('td');
    cell.appendChild(document.createTextNode(formatXCoordinate(x)));
    row.appendChild(cell);
  }

tbodyElem.appendChild(row);

// Remaining rows
  for (let y = pageBoard.height - 1; y >= 0; y--) {
    row = document.createElement('tr');
    let cell = document.createElement('td');
    cell.appendChild(document.createTextNode(y));
    row.appendChild(cell);

for (let x = 0; x < pageBoard.width; x++) {
      cell = document.createElement('td');
      cell.onmousedown = ((x, y) => {
        return function(ev) {
          let inc = 0;
          if (ev.button === 0) {
            inc = 1;
          } else if (ev.button === 2) {
            inc = -1;
          }
          pageBoard.grid[y * pageBoard.width + x] = (pageBoard.grid[y * pageBoard.width + x] + inc + TILE_COLORS.length) % TILE_COLORS.length;
          handleBoardChanged(x, y);
        };
      })(x, y);

cell.oncontextmenu = function() { return false; };
      row.appendChild(cell);
    }

tbodyElem.appendChild(row);
  }

handleBoardChanged();
}

function doSolve() {
  clearSolution();
  const solnTextElem = document.getElementById('solutiontext');
  const solnStepsElem = document.getElementById('solutionsteps');
  const boardsVisitedElem = document.getElementById('boardsvisited');

boardsVisitedElem.appendChild(document.createTextNode(`Boards visited: ${solution[1]}`));
}

function doImport() {
  const lines = document.getElementById('importexportbox').value.replace(/\s+$/, '').split('\n');
  if (lines.length !== pageBoard.height + 1) {
    alert(`Invalid number of lines (should be ${pageBoard.height + 1})`);
    return;
  }

const moves = parseInt(lines[0], 10);
  if (!/\d+/.test(lines[0]) || moves < 0 || moves > 100) {
    alert('Invalid number of moves');
    return;
  }

function doExample() {
  let index;
  do {
    index = Math.floor(Math.random() * EXAMPLE_PUZZLES.length);
  } while (index === currentExample);

document.getElementById('importexportbox').value = EXAMPLE_PUZZLES[index];
  doImport();

currentExample = index;
}

function doClear() {
  for (let i = 0; i < pageBoard.grid.length; i++) {
    pageBoard.grid[i] = 0;
  }
  handleBoardChanged();
}

// Update export text
  let exportStr = document.getElementById('nummoves').value;
  for (let y = 0; y < pageBoard.height; y++) {
    exportStr += '\n';
    for (let x = 0; x < pageBoard.width; x++) {
      const val = pageBoard.grid[(pageBoard.height - 1 - y) * pageBoard.width + x];
      if (val === 0) {
        exportStr += '.';
      } else {
        exportStr += String.fromCharCode('a'.charCodeAt(0) + val - 1);
      }
    }
  }
  document.getElementById('importexportbox').value = exportStr;

clearSolution();
  currentExample = -1;
}

function clearSolution() {
  removeChildren(document.getElementById('solutiontext'));
  removeChildren(document.getElementById('solutionsteps'));
  removeChildren(document.getElementById('boardsvisited'));
}

function formatXCoordinate(x) {
  const START = 'A'.charCodeAt(0);
  if (x < 26) {
    return String.fromCharCode(START + x);
  } else if (x < 702) {
    return String.fromCharCode(START + Math.floor((x - 26) / 26)) + String.fromCharCode(START + (x - 26) % 26);
  }

throw 'Invalid value';
}

function removeChildren(elem) {
  while (elem.firstChild !== null) {
    elem.removeChild(elem.firstChild);
  }
}

// Initialization
initHtmlBoard();

/* Puzzle board and solver */
function Board(grid, width, height, prevBoard, prevMove, depth) {
  const EMPTY = 0;
  const MINIMUM_RUN = 3;

if (grid === null) {
    grid = [];
    for (let i = 0; i < width * height; i++) {
      grid.push(0);
    }
  }
  dropTiles();

while (matchAndClear()) {
    if (!dropTiles()) {
      break;
    }
  }

this.width = width;
  this.height = height;
  this.grid = grid;
  this.prevBoard = prevBoard;
  this.prevMove = prevMove;
  this.depth = depth;

const self = this;

this.solve = function(moves) {
    const visited = {};
    visited[self] = true;
    const queue = [self];

// Breadth-first search
    while (queue.length > 0) {
      let board = queue.shift();
      if (board.isEmpty()) {  // Solution found
        const solution = [];
        while (board.prevBoard !== null) {
          solution.push(board.prevMove);
          board = board.prevBoard;
        }
        solution.reverse();
        return [solution, Object.keys(visited).length];
      } else if (board.depth < moves) {  // Enqueue neighbors
        const nextBoards = board.getNextBoards();
        nextBoards.forEach((next) => {
          if (!(next in visited)) {
            queue.push(next);
            visited[next] = true;
          }
        });
      }
    }
    return [null, Object.keys(visited).length];
  };

this.getNextBoards = function() {
    const result = [];
    for (let y = 0; y < height; y++) {
      for (let x = 0; x + 1 < width; x++) {
        const next = swap(x, y);
        if (next !== null) {
          result.push(next);
        }
      }
    }
    return result;
  };

function swap(x, y) {
    if (x < 0 || x + 1 >= width || y < 0 || y >= height) {
      throw 'Index out of bounds';
    }

if (grid[y * width + x + 0] === grid[y * width + x + 1]) {
      return null;
    }

const newGrid = grid.slice();  // Clone
    newGrid[y * width + x + 0] = grid[y * width + x + 1];
    newGrid[y * width + x + 1] = grid[y * width + x + 0];

return new Board(newGrid, width, height, self, [x, y], depth + 1);
  }

this.isEmpty = function() {
    for (let i = 0; i < grid.length; i++) {
      if (grid[i] !== EMPTY) {
        return false;
      }
    }
    return true;
  };

function dropTiles() {
    let changed = false;
    for (let y = 0; y < height; y++) {
      for (let x = 0; x < width; x++) {
        if (grid[y * width + x] === EMPTY) {
          continue;
        }

for (let i = y; i - 1 >= 0 && grid[(i - 1) * width + x] === EMPTY; i--) {
          grid[(i - 1) * width + x] = grid[i * width + x];
          grid[i * width + x] = EMPTY;
          changed = true;
        }
      }
    }
    return changed;
  }

function matchAndClear() {
    const toClear = [];
    for (let i = 0; i < grid.length; i++) {
      toClear.push(false);
    }

// Find horizontal matches
    for (let y = 0; y < height; y++) {
      for (let x = 0; x < width - MINIMUM_RUN + 1;) {
        const run = getRunLength(x, y, 1, 0);
        if (run >= MINIMUM_RUN) {
          for (let i = 0; i < run; i++) {
            toClear[y * width + x + i] = true;
          }
        }
        x += run;
      }
    }

// Find vertical matches
    for (let x = 0; x < width; x++) {
      for (let y = 0; y < height - MINIMUM_RUN + 1;) {
        const run = getRunLength(x, y, 0, 1);
        if (run >= MINIMUM_RUN) {
          for (let i = 0; i < run; i++) {
            toClear[(y + i) * width + x] = true;
          }
        }
        y += run;
      }
    }

// Clear tiles
    let cleared = false;
    for (let y = 0; y < height; y++) {
      for (let x = 0; x < width; x++) {
        if (toClear[y * width + x]) {
          grid[y * width + x] = EMPTY;
          cleared = true;
        }
      }
    }
    return cleared;
  }

this.toString = function() {
    let result = '';
    grid.forEach((item) => {
      result += item.toString();
    });
    return result;
  };
}

Moves: