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()It'll do recursions but it will return to the original grid. I did code this in python and it worked. I don't know why it wont work in javascript.
The problem is that your code will reset the solution that it finds. Although it prints it correctly, that output is made before the top-level call of the function returns. By the time it returns, all cells have been reverted to 0.
Your code needs to use the return value from the recursive call, and if it is true, it should stop looking further and certainly not put back a 0. It should instead immediately exit, and tell its own caller that the solution is there.
So:
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);
The next improvement, is to avoid the function from mutating a global variable. Maybe turn the logic into a class, making the grid an instance property.