Solving Sudoku with wave function collapse in JavaScript

In a previous article, we discussed how to validate a Sudoku board in JavaScript. Now, let's take it a step further and implement a Sudoku solver using the wave function collapse algorithm. This method, inspired by quantum mechanics, is not only efficient but also elegant, leveraging constraint propagation to fill in the board. Let's see how it works in JavaScript.
@Quick refresher
Wave function collapse is about reducing possibilities. Each empty cell starts with all possible digits (1-9). As we fill in cells, we propagate constraints to neighboring cells, shrinking their options. When a cell has only one possibility, we collapse it (set its value) and repeat the process.
This approach is similar to how you might solve Sudoku by hand: fill in what you know, then update the rest based on new information. The key steps are:

• Each cell is initialized with all possible values (1-9).

// List of all possible values for a Sudoku cell
const allValues = ['1', '2', '3', '4', '5', '6', '7', '8', '9'];

// Get used values in a row, column, and sub-box
const getUsedValues = (row, col, board) => {
  const usedValues = new Set();

  // Row and column checks
  for (let i = 0; i < 9; i++) {
    if (board[row][i] !== '.') usedValues.add(board[row][i]);
    if (board[i][col] !== '.') usedValues.add(board[i][col]);
  }

  // Sub-box check
  const boxRowStart = Math.floor(row / 3) * 3;
  const boxColStart = Math.floor(col / 3) * 3;
  for (let boxRow = 0; boxRow < 3; boxRow++) {
    for (let boxCol = 0; boxCol < 3; boxCol++) {
      const value = board[boxRowStart + boxRow][boxColStart + boxCol];
      if (value !== '.') usedValues.add(value);
    }
  }

  return usedValues;
};

// Get possible values for a cell
const getPossibleValues = (row, col, board) => {
  if (board[row][col] !== '.') return [board[row][col]];

  const usedValues = getUsedValues(row, col, board);
  // Remove used values from all possible values (constraint propagation)
  return allValues.filter(value => !usedValues.has(value));
};

// Find cell with the fewest possibilities
const findCandidate = board => {
  let minOptions = 10, cellPosition = null, possibleValues = [];

  // Iterate through the board to find the cell with the fewest options
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      // Only consider empty cells
      if (board[row][col] === '.') {
        const options = getPossibleValues(row, col, board);

        // If the cell has fewer options than the current minimum, update
        if (options.length < minOptions) {
          minOptions = options.length;
          cellPosition = [row, col];
          possibleValues = options;

          // If the cell has only one option, we can return immediately
          if (minOptions === 1) return { cellPosition, possibleValues };
        }
      }
    }
  }

  // If a candidate cell is found, return its position and possible values
  // If no empty cells are found, return null
  return cellPosition ? { cellPosition, possibleValues } : null;
};

// Recursive solver
const solveRecursively = board => {
  const nextCell = findCandidate(board);
  // If no cell found, the board is solved
  if (!nextCell) return true;

  // Get the cell position and possible values
  const [row, col] = nextCell.cellPosition;

  // Try each possible value for the cell
  for (const value of nextCell.possibleValues) {
    board[row][col] = value;
    // Recursively attempt to solve the board with this value
    if (solveRecursively(board)) return true;
    // If it didn't work, reset the cell and try the next value
    board[row][col] = '.';
  }

  // If no value worked, return false to backtrack
  return false;
};

const solveSudoku = board => {
  // Deep copy to avoid mutating input
  const boardCopy = board.map(row => row.slice());
  // Start the recursive solving process
  solveRecursively(boardCopy);
  //

Wave function collapse is about reducing possibilities. Each empty cell starts with all possible digits (1-9). As we fill in cells, we propagate constraints to neighboring cells, shrinking their options. When a cell has only one possibility, we collapse it (set its value) and repeat the process.
This approach is similar to how you might solve Sudoku by hand: fill in what you know, then update the rest based on new information. The key steps are:

• Each cell is initialized with all possible values (1-9).
• When a cell is filled, we propagate constraints to update neighboring cells, removing impossible values.
• We collapse cells with only one possibility. If no such cells exist, we look for the cell with the fewest possibilities and fill it.
• If we reach a point where no cells can be filled, we backtrack and try different values for previously filled cells.

From 30-seconds-of-code: sudoku-solver-wave-function-collapse