using stack

sudoku-solver.js

var Board = function(_m) {
    this.m = _m;

    this.rowCheck = function(r, v) {
        for (let i = 0; i < 9; i++) {
            if (this.m[r][i] == v) return false;
        }
        return true;
    }

    this.colCheck = function(c, v) {
        for (let i = 0; i < 9; i++) {
            if (this.m[i][c] == v) return false;
        }
        return true;
    }

    this.blockCheck = function(r, c, v) {
        let sr = Math.floor(r / 3) * 3;
        let sc = Math.floor(c / 3) * 3;
        for (let i = 0; i < 3; i++) {
            for (let j = 0; j < 3; j++) {
                if (this.m[sr + i][sc + j] == v) return false;
            }
        }
        return true;
    }

    this.validate = function(r, c, v) {
        return this.rowCheck(r, v) && this.colCheck(c, v) && this.blockCheck(r, c, v);
    }

    this.findNext = function() {
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (this.m[i][j] == 0) return i * 9 + j;
            }
        }
        return -1;
    }

    this.solve = function() {
        let steps = 0; // count the trial step
        let i = -1;
        let s = []; // stack to store trial steps
        let canSet = true; // found a value to put into the board
        let nextV = 0; // value to try for next finding
        do {
            if (canSet) i = this.findNext(); // if last step was successfully found a value 
            else {
                let r = Math.floor(i / 9);
                let c = i % 9;
                this.m[r][c] = 0; // unset the last position
                i = -1;
                while (s.length > 0) {
                    i = s.pop(); // get the top position of the stack
                    r = Math.floor(i / 9);
                    c = i % 9;
                    if (this.m[r][c] < 9) // check if still have value to try
                    {
                        nextV = this.m[r][c] + 1;
                        break;
                    }
                    this.m[r][c] = 0; // if there's no value to try, set the current block to 0, and pop the next
                }
            }

            if (i >= 0) {
                let r = Math.floor(i / 9);
                let c = i % 9;
                canSet = false;
                for (let v = nextV; v <= 9; v++) // try to put trial values into the selected position 
                {
                    steps++;
                    canSet = this.validate(r, c, v);
                    if (canSet) {
                        this.m[r][c] = v; // put the valid value into the position
                        s.push(i); // store the position to the stack
                        nextV = 0;
                        break;
                    }
                }
            } else break; // if there's no thing to try or already finished
        } while (i < 81);

        return steps;
    }
}

let m = [
    [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]
];

let b = new Board(m);
let nSteps = b.solve();
console.log(nSteps);