Me estoy devanando los sesos, pero no puedo ver dónde me equivoqué. Desde el registro de la consola, parece que es un problema cuando se trata de que el retroceso no funciona correctamente. Creo que tiene algo que ver con la forma en que estoy trabajando. con objeto de posición, cualquier ayuda sería apreciada,
Funciona hasta que se supone que funciona el retroceso, y puedo ver que, de hecho, retrocede 6 veces, pero la posición en realidad no retrocede y altera los números anteriores.
let grid = []; const solve = function (pos) { while (pos.x < 9 && pos.y < 9 && grid[pos.x][pos.y].value) { pos = incrementPos(pos); } // skip non-empty cells if (pos.y == 9) return true; for (let m = 1; m < 10; m++) { grid[pos.x][pos.y].value = m; console.log(pos, m); if (isValid(m, pos)) { if (solve(incrementPos(pos))) { return true; } } } console.log("start backtrack", pos); grid[pos.x][pos.y].value = ""; return false; }; function isValid(n, pos) { let valid = true; let row = checkRow(n, pos); let col = checkCol(n, pos); let block = checkBlock(n, pos); if (!row || !col || !block) { return false; } else { return true; } } function checkBlock(n, pos) { let startX = parseInt(pos.x / 3) * 3; let startY = parseInt(pos.y / 3) * 3; for (let x = startX; x < startX + 3; x++) { for (let y = startY; y < startY + 3; y++) { if ((grid[x][y].value === n) & (x !== pos.x) & (y !== pos.y)) { return false; } } } return true; } function checkRow(n, pos) { for (let t = 0; t < 9; t++) { if (grid[t][pos.y].value === n && t !== pos.x) { return false; } } return true; } function checkCol(n, pos) { for (let t = 0; t < 9; t++) { if ((grid[pos.x][t].value === n) & (t !== pos.y)) { return false; } } return true; } function incrementPos(pos) { if (pos.x < 8) { pos.x++; } else { pos.y++; pos.x = 0; } return pos; } const initGrid = function () { for (let x = 0; x < 9; x++) { let col = []; for (let y = 0; y < 9; y++) { let el = {}; el.locked = false; el.value = ""; el.location = document.querySelector("#r" + (y + 1) + "c" + (x + 1)); col.push(el); } grid.push(col); } displayGrid(); }; const displayGrid = function () { for (let x = 1; x < 10; x++) { for (let y = 1; y < 10; y++) { document.querySelector("#r" + y + "c" + x).textContent = grid[x - 1][y - 1].value; } } };Realmente no puedo entender lo que estás haciendo, es demasiado, sin embargo, no puedo ver dónde realmente estás restableciendo la posición. Estoy buscando algo como esto:
const getBlock = (block) => { if (block === 9) { return true } // you can use a total variable here to try it a couple of times before backtracking const valid = false ... if (valid) { getBlock(++block) } else { getBlock(--block) } }Ese código no es perfecto en absoluto, pero es solo para mostrarle la idea, debe aumentar el bloque si es válido y después de un par de iteraciones en las que no puede encontrar otro bloque después de eso, debe restablecer el bloque a la anterior y vuelva a intentarlo. El resultado con el retroceso es que si registra los bloques en la consola, debería ver algo como: 1 -> 2 -> 3 -> 4 -> 3 -> 4 -> 5 -> 4 -> 3 -> 4 -> 5 - > 6 -> ... una y otra vez hasta que finalmente encuentres una solución.
En su propio código, esperaría que fuera algo como:
if (solve(incrementPos(pos))) { return true } else { solve(decrementPos(pos)) // or something // otherwise you're not actually backtracking }Nota al margen, puede usar aritmética modular en lugar de bucles. Si sabe que está en un bloque específico, puede validar/invalidar inmediatamente y verificar si los valores existen en filas/columnas/diagonales correlacionadas sin bucles. Solo un consejo.