Recursion: Backtracking sudoku solver in JS

Question

I can't get this recursive algorithm working. It should solve a sudoku grid (a 2d array of ints). I've made the same in Java (but OOP of course) and it works fine. But in JS it doesn't. Values in the grid doesn't get changed and it never reaches the base case. The algorithm is solveSudoku - the base case is, when it searches through the grid but doesn't find any "empty" cells (with a value of '0').

I've put all the code in one file. Can you spot the error? I've been trying for a week now and about to abandom this little project.

"use strict";

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

// recursive algo
function solveSudoku(grid, row, col) {
    var cell = findUnassignedLocation(grid, row, col);
    row = cell[0];
    col = cell[1];

    // base case: if no empty cell  
    if (row == -1) {
        console.log("solved");
        return true;
    }

    for (var num = 1; num <= 9; num++) {

        if ( noConflicts(grid, row, col, num) ) {   
            grid[row][col] = num;

            if ( solveSudoku(grid, row, col) ) {                
                return true;
            }

                    // mark cell as empty (with 0)    
            grid[row][col] = 0;
        }
    }

    // trigger back tracking
    return false;
}


function findUnassignedLocation(grid, row, col) {
    var done = false;
    var res = [-1, -1];

    while (!done) {
        if (row == 9) {
            done = true;
        }
        else {
            if (grid[row][col] == 0) {
                res[0] = row;
                res[1] = col;
                done = true;
            }
            else {
                if (col < 8) {
                    col++;
                }
                else {
                    row++;
                    col = 0;
                }
            }
        }
    }

    return res;
}

function noConflicts(grid, row, col, num) {
    return isRowOk(grid, row, num) && isColOk(grid, col, num) && isBoxOk(grid, row, col, num);
}

function isRowOk(grid, row, num) {
    for (var col = 0; col < 9; col++)
        if (grid[row][col] == num)
            return false;

    return true;
}
function isColOk(grid, col, num) {
    for (var row = 0; row < 9; row++)
    if (grid[row][col] == num)
        return false;

    return true;    
}
function isBoxOk(grid, row, col, num) {
    row = (row / 3) * 3;
    col = (col / 3) * 3;

    for (var r = 0; r < 3; r++)
        for (var c = 0; c < 3; c++)
            if (grid[row + r][col + c] == num)
                return false;

    return true;
}

function printGrid(grid) {
    var res = "";

    for (var i = 0; i < 9; i++) {
        for (var j = 0; j < 9; j++) {
            res += grid[i][j];
        }
        res += "\n";
    }
    console.log(res);
}

No error msgs. It just prints out the grid unchanged. I'm using Chrome and FireFox. — olefrank
– olefrank, Commented Aug 24, 2013 at 16:15
The code seems fine. I can only assume this means that your particular Sudoku puzzle can't be solved naively. — Niet the Dark Absol
– Niet the Dark Absol, Commented Aug 24, 2013 at 16:16
Java can! Could it be that JS recursive abilities is limited in some way, like number of calls to stack is too limited etc.. — olefrank
– olefrank, Commented Aug 24, 2013 at 16:21
The code is almost fine, and the puzzle can indeed be solved by it :-) — 6502
– 6502, Commented Aug 24, 2013 at 16:37

6502 · Accepted Answer · 2013-08-24 16:33:55Z

5

It was tricky to find... but the problem is in

row = (row / 3) * 3;
col = (col / 3) * 3;

Javascript uses only floating point numbers so this is not doing what you think is doing.

The solution is

row = Math.floor(row / 3) * 3;
col = Math.floor(col / 3) * 3;

answered Aug 24, 2013 at 16:33

6502

115k17 gold badges177 silver badges277 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Niet the Dark Absol Over a year ago

Ah! Great catch! Not entirely sure how I missed that, considering it's a bit of a no-op with floats XD

Lithy · Accepted Answer · 2013-08-24 16:51:43Z

3

In javascript, numbers can't be forced to be integer so something like (a / 3) * 3 is not different from a. In isBoxOk, you need to replace

row = (row / 3) * 3;
col = (col / 3) * 3;

by

row = Math.floor(row / 3) * 3;
col = Math.floor(col / 3) * 3;

Furthermore, I think that you can simplify the findUnassignedLocation function :

function findUnassignedLocation(grid, row, col) {
    for (; row < 9 ; col = 0, row++)
        for (; col < 9 ; col++)
            if (grid[row][col] == 0)
                return [row, col];
    return [-1, -1];
}

edited Aug 24, 2013 at 16:51

answered Aug 24, 2013 at 16:40

Lithy

87712 silver badges24 bronze badges

Collectives™ on Stack Overflow

Recursion: Backtracking sudoku solver in JS

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related