let grid = [[2, 5, 0, 0, 3, 0, 9, 0, 1], [0, 1, 0, 0, 0, 4, 0, 0, 0], [4, 0, 7, 0, 0, 0, 2, 0, 8], [0, 0, 5, 2, 0, 0, 0, 0, 0], [0, 0, 0, 0, 9, 8, 1, 0, 0], [0, 4, 0, 0, 0, 3, 0, 0, 0], [0, 0, 0, 3, 6, 0, 0, 7, 2], [0, 7, 0, 0, 0, 0, 0, 0, 3], [9, 0, 3, 0, 0, 0, 6, 0, 4]] function possible(y, x, n){ for (let i = 0; i < 9; i++){ if (grid[i][x] === n){ return false } } for (let i = 0; i < 9; i++){ if (grid[y][i] === n){ return false } } let xx = (Math.floor(x / 3)) * 3 let yy = (Math.floor(y / 3)) * 3 for (let i = 0; i < 3; i++){ for (let j = 0; j < 3; j++){ if (grid[yy + i][xx + j] === n){ return false } } } return true } function solve(){ for (let y = 0; y < 9; y++){ for (let x = 0; x < 9; x++){ if (grid[y][x] === 0){ for (let n = 1; n < 10; n++){ if (possible(y, x, n)){ grid[y][x] = n solve() grid[y][x] = 0 } } return } } } console.log(grid) } solve()Hará recursiones pero volverá a la cuadrícula original. Codifiqué esto en python y funcionó. No sé por qué no funcionará en javascript.
El problema es que su código restablecerá la solución que encuentre. Aunque lo imprime correctamente, esa salida se realiza antes de que regrese la llamada de nivel superior de la función. Cuando regresa, todas las celdas se han revertido a 0.
Su código necesita usar el valor de retorno de la llamada recursiva, y si es true , debería dejar de buscar más y ciertamente no volver a poner un 0. En su lugar, debería salir inmediatamente y decirle a su propio llamador que la solución está ahí.
Asi que:
let grid = [[2, 5, 0, 0, 3, 0, 9, 0, 1], [0, 1, 0, 0, 0, 4, 0, 0, 0], [4, 0, 7, 0, 0, 0, 2, 0, 8], [0, 0, 5, 2, 0, 0, 0, 0, 0], [0, 0, 0, 0, 9, 8, 1, 0, 0], [0, 4, 0, 0, 0, 3, 0, 0, 0], [0, 0, 0, 3, 6, 0, 0, 7, 2], [0, 7, 0, 0, 0, 0, 0, 0, 3], [9, 0, 3, 0, 0, 0, 6, 0, 4]] function possible(y, x, n){ for (let i = 0; i < 9; i++){ if (grid[i][x] === n){ return false } } for (let i = 0; i < 9; i++){ if (grid[y][i] === n){ return false } } let xx = (Math.floor(x / 3)) * 3 let yy = (Math.floor(y / 3)) * 3 for (let i = 0; i < 3; i++){ for (let j = 0; j < 3; j++){ if (grid[yy + i][xx + j] === n){ return false } } } return true } function solve(){ for (let y = 0; y < 9; y++){ for (let x = 0; x < 9; x++){ if (grid[y][x] === 0){ for (let n = 1; n < 10; n++){ if (possible(y, x, n)){ grid[y][x] = n; if (solve()) return true; // <--- success! grid[y][x] = 0; } } return false; // <-- make it boolean } } } return true; // grid is complete! } solve(); for (let row of grid) console.log(...row);La siguiente mejora es evitar que la función mute una variable global. Tal vez convertir la lógica en una clase, convirtiendo la cuadrícula en una propiedad de instancia.