I'm racking my brain but I can't see where I've gone wrong, from the console log it appears it's an issue when it comes to backtracking not working correctly, I think it has something to do with how I'm working with position object, any help would be appreciated,
It works up until the backtracking is supposed to work, and I can see it does infact backtrack 6 times, but the position doesn't actually go back and alter the previous numbers
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;
}
}
};
I can't really figure out what you're doing, it's too much, however I can't see where you're actually resetting the position. I'm looking for something like this:
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)
}
}
That code isn't perfect at all but it's just to show you the idea, you should be increasing the block if it's valid and after a couple of iterations where you can't find another block after that you should reset the block back to the previous one and try again. The result with backtracking is that if you console log the blocks you should see something like: 1 -> 2 -> 3 -> 4 -> 3 -> 4 -> 5 -> 4 -> 3 -> 4 -> 5 -> 6 -> ... on and on back and forth until you eventually find a solution.
In your own code I'd expect it to be something like:
if (solve(incrementPos(pos))) {
return true
} else {
solve(decrementPos(pos)) // or something
// otherwise you're not actually backtracking
}
Side note, you can use modular arithmetic instead of loops. If you know that you're in a specific block then you can immediately validate/invalidate and check if the values exist in correlating rows/columns/diagonals without any loops. Just a tip.