Sudoku Solver: Problem with completing certain cells

Question

I have a problem with my sudoku solver and it involves the backtracking mechanism of the algorithm. Currently, I can get my sudoku board partially filled, but I run into a problem where all of the guesses in a certain cell are bad, and it leaves the space blank and continues to the next cell.

Here is the starting board:

let sudoku = [[6, 0, 5, 7, 0, 0, 1, 3, 2],
              [7, 0, 0, 6, 0, 0, 5, 0, 8],
              [0, 1, 9, 3, 0, 0, 0, 0, 4],
              [0, 2, 0, 0, 0, 3, 0, 0, 0],
              [0, 7, 3, 9, 0, 0, 2, 5, 0],
              [0, 5, 1, 2, 0, 0, 0, 0, 9],
              [5, 0, 8, 0, 0, 0, 0, 2, 0],
              [0, 4, 0, 0, 7, 6, 9, 1, 5],
              [0, 9, 0, 0, 4, 0, 6, 8, 0]];

Here is the result

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

0s are blank spaces. As you can see, this result is not a solved sudoku puzzle.

Here is my current algorithm:

let sudoku = [[6, 0, 5, 7, 0, 0, 1, 3, 2],
              [7, 0, 0, 6, 0, 0, 5, 0, 8],
              [0, 1, 9, 3, 0, 0, 0, 0, 4],
              [0, 2, 0, 0, 0, 3, 0, 0, 0],
              [0, 7, 3, 9, 0, 0, 2, 5, 0],
              [0, 5, 1, 2, 0, 0, 0, 0, 9],
              [5, 0, 8, 0, 0, 0, 0, 2, 0],
              [0, 4, 0, 0, 7, 6, 9, 1, 5],
              [0, 9, 0, 0, 4, 0, 6, 8, 0]];

function possibleCandidate(x, y, n) {
  for(let i = 0; i < sudoku[y].length; i++) {
    if(sudoku[y][i] == n) {
      return false;
    }
  }

  for(let i = 0; i < sudoku.length; i++) {
    if(sudoku[i][x] == n) {
      return false;
    }
  }

    // For 3x3 squares
    let baseX = Math.floor(x / 3) * 3;
    let baseY = Math.floor(y / 3) * 3;

    for(let a = 0; a < 3; a++) {
      for(let b = 0; b < 3; b++) {
        // add incremented values until reaching 3 to check if the value we are checking for is in the square
        if(sudoku[baseY + a][baseX + b] == n) {
          return false;
        }
      }
    }

    return true;
}

function solve() {
  let prev = [];
  let tried;
  for(let i = 0; i < sudoku.length; i++) {
    for(let j = 0; j < sudoku[i].length; j++) {
      if(sudoku[i][j] == 0) {
        for(let l = 0; l < 10; l++) {

          if(possibleCandidate(j, i, l) && l !== tried) {
            if(j == 4 && i == 0) {
              console.log(l);
            }
            prev = [i, j];
            tried = l;
            sudoku[i][j] = l;
            break;
          }
        }
        // return;
      }
    }
  }
  return true;
}

possibleCandidate(1, 0, 6);
solve();
console.log(sudoku);

EDIT:

The possibleCandidate() function is working properly, I think the problem stems specifically from the solve() function.

Answer 1

The problem is that your algorithm is "greedy": you assume that if a value is possible, that it must be right. This is not true.

For the example sudoku, it goes wrong when arriving at row 1, column 2. The algorithm decides that 2 can be placed there. But it ignores that 4 can be placed there as well. Which of the two is it? Well, the 4 cannot be placed in the other free square in that 3x3 box (in row 3, col 1), so the 4 can only be placed in row 1, column 2, thereby excluding the option that 2 should be placed there.

Therefore your algorithm is (much) too optimistic. It should consider also the other alternatives. There are lots of solvers. Even on Stack Overflow you should be able to find some. They are based on recursion and backtracking.

So you need to iterate over all values that pass the possibleCandidate test, and then call the function recursively for the next open square of the board. If that recursive call comes back with a failure indication, continue the loop to find other values that pass the possibleCandidate test, and call the function recursively again... until it returns success.

A recursive function will stop making a recursive call, when either:

• it finds that the whole board is filled: it will then return success to the caller, which will do the same, ... backtracking the whole way out of recursion

• none of the values that pass the possibleCandidate test get a success from the recursive call. In that case the function returns a failure to the caller, which will then continue its own loop, ...etc.

You can find solutions also on Stack Overflow, such as in Python.