Jogando com Probabilidades: Como o Wave Function Collapse funciona no Sudoku

Introdução:

O que raios é Wave Function Collapse

Os Bumps na Estrada

class SudokuSolver {
  constructor(initialGrid) {
    this.grid = initialGrid;
    this.possibleNumbers = new Map()
  }

  initialize() {
		// Inicializando colocando as possibilidades totais aonde inicialmente não existe numero
		// no grid, lembrando que 0 no caso é considerado como espaço vazio aqui
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (this.grid[row][col] === 0) {
          this.possibleNumbers.set(`${row},${col}`, new Set([1,2,3,4,5,6,7,8,9]))
        } else {
          this.possibleNumbers.set(`${row},${col}`, new Set([this.grid[row][col]]))
        }
      }
    }
		
		// Após inicializado, fiz a primeira leva de propagação, eliminando números repetidos
		// dentro da regra do jogo, entenda mais na func. de propagação
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (this.grid[row][col] !== 0) { 
          this.propagate(row, col, this.grid[row][col])
        }
      }
    }
  }

  propagate(row, col, number) {
		// Aqui está basicamente a regra do jogo Sudoku, linhas não podem conter o mesmo número
		// e nem colunas, alem disso, o jogo 9x9 é dividido em sub grids de 3x3, aonde tambem
		// não pode ter o número repetido 
    for (let k = 0; k < 9; k++) {
      this.possibleNumbers.get(`${row},${k}`)?.delete(number)
      this.possibleNumbers.get(`${k},${col}`)?.delete(number)
    }

    // Subgrid
    let subgridRow = Math.floor(row / 3) * 3
    let subgridCol = Math.floor(col / 3) * 3

    for (let i = 0; i < 3; i++) { 
      for (let j = 0; j < 3; j++) {
        this.possibleNumbers.get(`${subgridRow + i},${subgridCol + j}`)?.delete(number)
      }
    }
  }

  collapse() {
		// Aqui é o momento da mágica, inicialmente eu vejo todas as celulas e verifico a que tem a menor
		// possibilidade para colocarmos um valor (numa WCF o ideal min. é 1)
    let minOptions = 10
    let cellToCollapse = null

    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        let possibilities = this.possibleNumbers.get(`${row},${col}`)
        if (possibilities.size >= 1 && possibilities.size < minOptions) {
          minOptions = possibilities.size
          cellToCollapse = {row, col}
        }
      }
    }

		// Encontrado o elemento com menor "entropia", adiciono um valor, propago seguindo a regra
		// do jogo
    if (cellToCollapse) {
      let row = cellToCollapse.row
      let col = cellToCollapse.col
      let possibilities = Array.from(this.possibleNumbers.get(`${row},${col}`))
      let rowlapseValue = possibilities[0]

      this.grid[row][col] = rowlapseValue
      this.possibleNumbers.set(`${row},${col}`, new Set([rowlapseValue]))
      this.propagate(row, col, rowlapseValue)
    }
  }

  isSolved() {
		// Enquanto ainda tiver algum valor sem preencher ou com possibilidades, continuo tentando
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (this.grid[row][col] === 0 || this.possibleNumbers.get(`${row},${col}`).size > 1) {
          return false
        }
      }
    }

    return true
  }

  solve() {
		// Aqui é simples, tentar resolver até não poder mais (coloquei um tempo de 5 segundos, se passar
		// paro o solver pois ou o sudoku é daqueles cabeçudos ou alguma coisa deu errado
    const startTime = Date.now();
    const timeLimit = 5000;

    while (!this.isSolved()) {
      if (Date.now() - startTime > timeLimit) {
        throw new Error('Sudoku não resolvido no tempo limite');
      }
      this.collapse()
    }
  }

  showGrid() {
		// Função simples para verificar como "ta ficando"
    let grid = ''
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        grid += `${this.grid[row][col]} `
      }
      grid += `\n`
    }
    console.log(grid)
  }

  returnSolution() {
		// O Kata exige um retorno como array
    const arr = []
    for (let row = 0; row < 9; row++) {
      let line = []
      for (let col = 0; col < 9; col++) {
        line.push(this.grid[row][col])
      }
      arr.push(line)
    }
    return arr
  }
}

Conclusão