Sudoku solver works in python but not javascript

Question

So I was following along with a Computerphile video about writing a sudoku solver and managed to get the code working in python, here's what I got:

def possible(grid, y, x, n):
for i in range(0,9):
    if grid[y][i] == n:
        return False
    if grid[i][x] == n:
        return False
x0 = (x//3)*3
y0 = (y//3)*3
for i in range(0,3):
    for j in range(0,3):
        if grid[y0+i][x0+j] == n:
            return False
return True

def solver(grid):
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1,10):
                    if possible(grid, y, x, n):
                        grid[y][x] = n
                        solver(grid)
                        grid[y][x] = 0
                return
    print(np.matrix(grid))

This code works properly. But I wanted to try to get this working in a web application, so I translated it to Javascript like this:

function possible(board, y, x, n) {
    for(i = 0; i < 9; i++) {
        if(board[y][i] === n) {
            return false;
        }
        if(board[i][x] === n) {
            return false;
        }
    }
    y0 = Math.floor(y/3)*3;
    x0 = Math.floor(x/3)*3;
    for(i = 0; i < 3; i++) {
        for(j = 0; j < 3; j++) {
            if(board[i+y0][j+x0] === n) {
                return false;
            }
        }
    }
    return true;
} 

function solver(board) {
    for(y = 0; y < 9; y++) {
        for(x = 0; x < 9; x++) {
            if(board[y][x] === 0) {
                for(n = 1; n < 10; n++) {
                    if(possible(board, y, x, n)) {
                        board[y][x] = n;
                        solver(board);
                        board[y][x] = 0;
                    }
                }
                return;
            }
        }
    }
    console.log(board);
}

As far as I can see, these functions are exactly the same, and since it works in Python I can't figure out why it doesn't work in JavaScript. In JS, it seems that it never even reaches the console.log(board) line, so I'm wandering if I'm hitting max recursion depth or something simple like that.

For reference, here is a grid that works in the Python solver:

grid = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

// in Python is floor division so I figured that is how I should write it in JavaScript. And range() excludes the last number so range(9) is 0-8 and range(1,10) is 1-9. I did try getting rid of the floor and add 1 to the ranges anyway and that didn't seem to have an affect. — Andrew Player, Dec 11 '20 at 03:33
`In JS, it seems that it never even reaches the console.log(board) line` ... possibly a recursion issue, like an infinite loop, but you would get a js timeout like error usually if so, so I'm thinking a "syntax error" instead. ......... Can you include your complete JS source in your question on an edit? — GetSet, Dec 11 '20 at 03:46
Those two functions plus the grid are the whole source. I was just including it in a blank html file and running solver(grid) in the chrome console. — Andrew Player, Dec 11 '20 at 04:01
Ok. I will try to reproduce from my machine. I presume you have `` tags? — GetSet, Dec 11 '20 at 04:02
Yeah, the function runs and I get a return undefined from the return statement in the function. I also get console.log() outputs when I add them in the function, so it is running and everything. — Andrew Player, Dec 11 '20 at 04:10
Ok. I ran your code. Your `return` should be `return true` best guess. Inside your `solver()` function. Which would also mean, around area you do `console.log()` you should `return false`. ......... You get "undefined" because js doesn't presume "true". — GetSet, Dec 11 '20 at 04:24

score 0 · Accepted Answer · answered Dec 11 '20 at 05:00

If you are using for loops inside a function, var will create a local variable, "no var" will look up the scope chain until it finds the variable or hits the global scope. Meaning that you need to declare the var when creating your variables inside the for loops to avoid one loop messing with the other around. Read more here

So your code should look like this:

function possible(board, y, x, n) {
    for (var i = 0; i < 9; i++) {
        if (board[y][i] === n) {
            return false;
        }
        if (board[i][x] === n) {
            return false;
        }
    }
    y0 = Math.floor(y / 3) * 3;
  
    x0 = Math.floor(x / 3) * 3;
    for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {
            if (board[y0+i][x0+j] === n) {
                return false;
            }
        }
    }
    return true;
}

function solver(board) {
    for (var y = 0; y < 9; y++) {
        for (var x = 0; x < 9; x++) {
            if (board[y][x] === 0) {
                for (var n = 1; n < 10; n++) {
                  
                    if (possible(board, y, x, n)) {
                        board[y][x] = n;
                        solver(board);
                        board[y][x] = 0; 
                    } 

                }
              return
            }
        }
    }
    console.log(board);
}

Sudoku solver works in python but not javascript

1 Answers1