let puzzle = [ [0, 0, 7, 0, 0, 3, 5, 0, 0], [6, 0, 5, 4, 0, 8, 3, 0, 2], [0, 0, 4, 5, 2, 0, 9, 0, 6], [0, 0, 0, 0, 7, 1, 2, 0, 9], [0, 0, 0, 0, 0, 0, 0, 0, 0], [8, 0, 9, 2, 3, 0, 0, 0, 0], [9, 0, 1, 0, 8, 5, 6, 0, 0], [7, 0, 3, 9, 0, 2, 8, 0, 5], [0, 0, 8, 7, 0, 0, 1, 0, 0] ]; class Sudoku { constructor(puzzle) { this.sudoku = puzzle; } isPossible(y, x, n) { for (let i = 0; i < 9; i++) { if (this.sudoku[y][i] == n) return false; } for (let i = 0; i < 9; i++) { if (this.sudoku[i][x] == n) return false; } let y0 = (Math.floor(y / 3) * 3); let x0 = (Math.floor(x / 3) * 3); for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { if (this.sudoku[y0 + i][x0 + j] == n) return false; } } return true; } solve() { for (let y = 0; y < 9; y++) { for (let x = 0; x < 9; x++) { if (this.sudoku[y][x] == 0) { for (let n = 1; n <= 9; n++) { if (this.isPossible(y, x, n)) { this.sudoku[y][x] = n; this.solve(); this.sudoku[y][x] = 0; } } return; } } } console.table(this.sudoku); } } let s = new Sudoku(puzzle); s.solve(); Esto funciona bien de la forma en que está escrito. Sin embargo, la depuración muestra que después de console.table , el código sigue ejecutándose y devuelve la matriz a su estado original. Pero, la línea console.table nunca se vuelve a ejecutar. Entonces, fuera del método de solve , this.sudoku es solo la matriz de puzzle original. ¿Por qué está pasando esto? Después de la salida, ¿qué está causando que el código siga ejecutándose? ¿Cómo es que nunca vuelve al final ( console.table ) y cómo puedo detenerlo una vez que haya resuelto el rompecabezas?
Es importante ver que la salida de la consola se alcanza si y solo si no hay más campos abiertos en la tabla (mediante programación. elementos de matriz establecidos en cero).
En cualquier otro caso, el flujo de control regresa de la invocación de la función actual antes de que se alcance la instrucción de salida.
El algoritmo recursivo se basa en la idea de que para resolver un problema de sudoku dado, eliges un campo abierto, eliges el primer número entre 1 y 9 que mantiene el cuadro consistente con las reglas e intentas resolver este nuevo rompecabezas llamando recursivamente al solucionador. La terminación está garantizada ya que con cada llamada recursiva hay un campo libre menos.
Una vez completada una llamada recursiva, se retira la elección realizada inmediatamente antes de la llamada y se prueban las posibilidades restantes para asignar un número a la posición, comprobando una vez más la consistencia y llamando recursivamente al solucionador. De esta manera, se encontrarán todas las soluciones al rompecabezas original.
El solucionador es eficiente en el sentido de que visita cada configuración que no admite otro nivel de recursividad (es decir, que es una solución o un callejón sin salida) solo una vez. Hay exactamente 1 secuencia en la que se llenarán las posiciones de configuración que están abiertas en el rompecabezas de inicio.
de un troll
Lo haré de esta manera, simplemente agregando un poco de descanso...
const puzzle = [ [ 0, 0, 7, 0, 0, 3, 5, 0, 0] , [ 6, 0, 5, 4, 0, 8, 3, 0, 2] , [ 0, 0, 4, 5, 2, 0, 9, 0, 6] , [ 0, 0, 0, 0, 7, 1, 2, 0, 9] , [ 0, 0, 0, 0, 0, 0, 0, 0, 0] , [ 8, 0, 9, 2, 3, 0, 0, 0, 0] , [ 9, 0, 1, 0, 8, 5, 6, 0, 0] , [ 7, 0, 3, 9, 0, 2, 8, 0, 5] , [ 0, 0, 8, 7, 0, 0, 1, 0, 0] ]; const Sudoku = (()=> { let grid = null , solved = false ; const isPossible = (row, col, num) => { for (let c in grid) if (grid[row][c] === num) return false; for (let r in grid) if (grid[r][col] === num) return false; let row0 = 3*(0|row/3) , col0 = 3*(0|col/3) ; for (let c of [0,1,2]) for (let r of [0,1,2]) if (grid[row0 + r][col0 + c] === num) return false; return true; } const solve = () => { for (let row in grid) { if (solved) break for (let col in grid) { if (grid[row][col] == 0) { if (solved) break for (let num of [1,2,3,4,5,6,7,8,9]) if (isPossible(row, col, num)) { grid[row][col] = num; solve(); if (!solved) grid[row][col] = 0; }; return; }; } } solved = true } return (puzzle)=> { grid = puzzle solved = false solve() // console.table(grid); doesn't work on snippet for (let row of grid) console.log(JSON.stringify(row)) } })() Sudoku(puzzle); .as-console-wrapper {max-height: 100% !important;top: 0;} .as-console-row::after {display: none !important;}