Solution to https://www.codewars.com/kata/57ff9d3b8f7dda23130015fa

solveMine.js

/**
 * Return a table string representation of the matrix
 * @param {Array} matrix The matrix
 * @param {String} prop The property to print
 */
function stringifyMatrix(matrix, prop = "originalValue") {
  return matrix
    .map((e) => e.map((e) => (prop === "" ? String(e) : e[prop])))
    .join("\n")
    .replace(/\,/g, " ");
}

/**
 * Generate all possibile unique permutation of a given set
 * @param {Array} elements The combination
 */
function* permutations(elements, map = new Map()) {
  if (elements.length === 1) {
    yield elements;
  } else {
    const [first, ...rest] = elements;
    for (const perm of permutations(rest, map)) {
      for (let i = 0; i < elements.length; i++) {
        const start = perm.slice(0, i);
        const rest = perm.slice(i);
        const val = [...start, first, ...rest];
        // const key = JSON.stringify(val);
        // Use join since we know that inner elements are primites
        const key = val.join(",");
        if (!map.has(key)) {
          map.set(key, val);
          yield val;
        }
      }
    }
  }
}

/**
 * Solver
 * @param {Array} map The matrix
 * @param {Number} totalMinesCount Number of total mines to discover
 */
function solveMine(map, totalMinesCount) {
  let discoveredMinesCount = 0;
  let discoveredMinesThisLoopCount = 0;
  let safeCellsDiscoveredCount = 0;
  let safeCellsDiscoveredThisLoopCount = 0;

  // Map the map into a useful object matrix containing other sub-properties
  // that will be used to keep track of current state
  const matrix = map.split("\n").map((row, x) =>
    row.split(" ").map((cell, y) => {
      const finite = isFinite(cell);
      const value = finite ? Number(cell) : cell;
      return {
        // This is the number that will keep track of how many REMAINING mines we have around
        value,
        // Boolean to check if this cell has been discovered as number
        discovered: finite,
        // Boolean to check if this cell has been marked as mine
        mine: cell === "x",
        // Coordinates
        x,
        y,
        // Original value returned from open that will never be touched
        originalValue: value,
        // Set of cells around that are marked as mine
        minesArounds: new Set(),
      };
    })
  );

  // Constants
  const maxRow = matrix.length;
  const maxCol = matrix[0].length;
  // All possible XY directions to check around
  const directions = [-1, 0, 1];

  /**
   * Generate every cell around the called cell, excluding out-of-boundaries index
   * @param {Cell} cell
   * @param {Function} callback
   */
  const accessCellsAround = function* (cell) {
    for (let x of directions) {
      for (let y of directions) {
        // Ignore myself
        if (x === 0 && y === 0) continue;
        const i = cell.x + x;
        const j = cell.y + y;
        if (i < 0 || j < 0 || i >= maxRow || j >= maxCol) continue;
        yield matrix[i][j];
      }
    }
  };

  /**
   * Mark a cell as safe, so open it and get the number behind it
   * @param {Cell} cell
   */
  const markCellAsSafe = (cell) => {
    // Don't do it if it's alread done
    if (cell.discovered) return;
    cell.originalValue = Number(open(cell.x, cell.y, matrix));
    // The real value is decreased by taking into consideration how many mines
    // we've already discovered around it
    cell.value = cell.originalValue - cell.minesArounds.size;
    cell.discovered = true;
    cell.mine = false;
    safeCellsDiscoveredCount++;
    safeCellsDiscoveredThisLoopCount++;
  };

  /**
   * Mark a cell as mine
   * @param {Cell} cell
   */
  const markCellAsMine = (cell) => {
    // Don't do it if it's alread done
    if (cell.mine) return;
    cell.value = cell.originalValue = "x";
    cell.mine = true;
    discoveredMinesCount++;
    discoveredMinesThisLoopCount++;
    decreaseCellsValueAroundMine(cell);
  };

  /**
   * Decrease the value of the discovered cells around a mine
   * to keep track of remaining mines to discovered around it
   * @param {Cell} cell
   */
  const decreaseCellsValueAroundMine = (cell) => {
    for (const cellAround of accessCellsAround(cell)) {
      if (!cellAround.mine) {
        cellAround.minesArounds.add(cell);
        // Decrease the value if we know how many mines we have
        if (cellAround.discovered) {
          cellAround.value--;
        }
      }
    }
  };

  /**
   * Expand the remaining safe cells to return the final matrix
   */
  const expandRemainingSafeCells = () => {
    for (const row of matrix) {
      for (const cell of row) {
        if (!cell.discovered && !cell.mine) {
          markCellAsSafe(cell);
        }
      }
    }
  };

  /**
   * Open all cells with "0" recursively
   */
  const openAllZeros = () => {
    let safeCellsBefore;

    do {
      safeCellsBefore = safeCellsDiscoveredThisLoopCount;
      for (const row of matrix) {
        for (const cell of row) {
          if (cell.discovered && cell.value === 0) {
            for (const cellAround of accessCellsAround(cell)) {
              if (!cellAround.discovered && !cellAround.mine) {
                markCellAsSafe(cellAround);
              }
            }
          }
        }
      }
    } while (safeCellsDiscoveredThisLoopCount > safeCellsBefore);
  };

  /**
   * Try to discover "sure" mines around a cell
   * The assumption is simple: if a discovered cell has a number
   * of undiscovered cells around it that is equal to the number in this cell,
   * then they're all mines
   */
  const discoverMines = () => {
    // Skip this algorithm if we're already done
    if (discoveredMinesCount === totalMinesCount) {
      return;
    }

    for (const row of matrix) {
      for (const cell of row) {
        if (cell.discovered && cell.value > 0) {
          // Count undiscovered squares around
          let undiscoveredCells = [];
          for (const cellAround of accessCellsAround(cell)) {
            if (!cellAround.discovered && !cellAround.mine) {
              undiscoveredCells.push(cellAround);
            }
          }
          if (
            undiscoveredCells.length > 0 &&
            undiscoveredCells.length === cell.value
          ) {
            for (let undiscCell of undiscoveredCells) {
              if (!undiscCell.mine) {
                markCellAsMine(undiscCell);
              }
            }
          }
        }
      }
    }
  };

  /**
   * Towards the end of the game, we have what we define as "border",
   * a set of cells that live on the edge of discovered cells
   * We have to look-up for remaining mines on this borde
   */
  const getBorders = () => {
    const border = new Set();
    for (const row of matrix) {
      for (const cell of row) {
        if (!cell.discovered && !cell.mine) {
          let freeCell = true;
          for (const cellAround of accessCellsAround(cell)) {
            if (cellAround.discovered || cell.mine) {
              freeCell = false;
              break;
            }
          }
          // If we have only "undiscovered" cells around,
          // this cell lives in a "deep" border,
          // therefore it hasn't useful info we can rely on
          if (!freeCell) {
            border.add(cell);
          }
        }
      }
    }
    return border;
  };

  /**
   * Check if this combination is valid and all constraints are respected
   * @param {Array} combination
   * @param {Set} border
   */
  const isSolutionValid = (combination, border) => {
    let index = 0;
    const cellsToCheck = new Set();

    for (const cell of border) {
      const supposelyMine = Boolean(combination[index++]);

      for (const cellAround of accessCellsAround(cell)) {
        if (cellAround.discovered) {
          // Reset the set if it's referring to another combination
          if (cellAround.supposelyMinesAroundCombination !== combination) {
            cellAround.supposelyMinesAroundCombination = combination;
            cellAround.supposelyMinesAround = new Set();
          }
          if (supposelyMine) {
            cellAround.supposelyMinesAround.add(cell);
          }
          cellsToCheck.add(cellAround);
        }
      }
    }

    // For every cell, check the constraint
    for (const cellToCheck of cellsToCheck) {
      if (cellToCheck.supposelyMinesAround.size !== cellToCheck.value) {
        // Instant return if we failed a constraint
        return false;
      }
    }

    return true;
  };

  /**
   * Try all possible combination for a specific set of cells
   * @param {Set} border
   */
  const brute = (border) => {
    const solutions = [];

    // Get total remaining cells to discover
    let totalRemainingCells = 0;
    for (let row of matrix) {
      for (const cell of row) {
        if (!cell.discovered && !cell.mine) {
          totalRemainingCells++;
        }
      }
    }
    // This is the number of cells that are part of the "deep" border
    const totallyUnknownCells = totalRemainingCells - border.size;

    // The number of possibile combinations is the product
    // of all possible placements of remaning mines,
    // but we have to consider that some mines can fall in the "deep" border
    // therefore we have to cycle also through all possible count of mines
    for (
      let noOfMines = totalMinesCount - discoveredMinesCount;
      noOfMines >=
        Math.max(
          0,
          totalMinesCount - discoveredMinesCount - totallyUnknownCells
        ) && border.size - noOfMines >= 1;
      noOfMines--
    ) {
      const initialComb = new Array(border.size - noOfMines)
        .fill(0)
        .concat(new Array(noOfMines).fill(1));
      for (const combination of permutations(initialComb)) {
        if (isSolutionValid(combination, border)) {
          solutions.push(combination);
        }
      }
    }

    return solutions;
  };

  /**
   * Towards the end of the game, try the brute-force algorithm
   */
  const bruteSolver = () => {
    // Skip this algorithm if we're already done
    if (discoveredMinesCount === totalMinesCount) {
      return;
    }

    const border = getBorders();
    if (border.size === 0) {
      return;
    }

    // Get all possibile solutions for this border
    const solutions = brute(border);

    // If brute is not able to find any solution, we're done here
    if (solutions.length === 0) {
      return;
    }

    // If we have more solutions, it can means two things:
    // - the puzzle is unsolvable
    // - we have to find the next safe cell to click to know more about the puzzle
    if (solutions.length > 1) {
      // Search for cells that are marked as SAFE in every solution
      // If we're able to find them, it means that we're sure it's a safe cell
      const sumSolutions = new Array(border.size).fill(0);
      for (const s of solutions) {
        for (let i = 0; i < s.length; i++) {
          sumSolutions[i] += s[i];
        }
      }

      let index = 0;
      for (const cell of border) {
        // If the sum is ZERO, this is a safe cell!
        if (sumSolutions[index++] === 0) {
          if (!cell.discovered && !cell.mine) {
            markCellAsSafe(cell);
          }
        }
      }

      // We've done it, go back to easy solver
      return;
    }

    if (solutions.length === 1) {
      const [solution] = solutions;

      let index = 0;
      for (const cell of border) {
        if (solution[index++] === 1) {
          if (!cell.mine) {
            markCellAsMine(cell);
          }
        } else {
          if (!cell.discovered) {
            markCellAsSafe(cell);
          }
        }
      }

      // We've done it, go back to easy solver
      return;
    }
  };

  /**
   * Global loop solver
   */
  const solver = () => {
    while (true) {
      // Loop through this easy-solver the more we can
      do {
        discoveredMinesThisLoopCount = 0;
        safeCellsDiscoveredThisLoopCount = 0;
        openAllZeros();
        discoverMines();
      } while (
        discoveredMinesThisLoopCount > 0 ||
        safeCellsDiscoveredThisLoopCount > 0
      );

      discoveredMinesThisLoopCount = 0;
      safeCellsDiscoveredThisLoopCount = 0;
      bruteSolver();

      // If brute wasn't able to find safe cells to click on it
      // it means we're on the same stage as before, therefore we're done here
      if (safeCellsDiscoveredThisLoopCount === 0) {
        return;
      }
    }
  };

  // ---- START ALGORITHM -----
  solver();

  // If we have not discovered all mines, this puzzle can't be solved
  if (discoveredMinesCount < totalMinesCount) {
    return "?";
  }

  // Good! We've discovered all mines, it means we can safely open all remaining cells
  // to make sure we return the full discovered cells
  expandRemainingSafeCells();

  // Return the string representation
  return stringifyMatrix(matrix);
}