Determine if Sudoku is solvable in JavaScript

Question

This is a problem from Pramp. I need to determine if a sudoku is solvable or not (not like LEETcode question where I just need to see if a board is valid or not).

Below is my code in JavaScript, using recursion. I'm following the logic suggested on Pramp, which is to create a helper function getCandidates() to find all candidate numbers that can go into an empty space. Then in the actual sudokuSolve() function, find the empty space with the smallest set of candidates, input those candidates into the empty space, and then try to solve the board using recursion. If it works, the board is solvable.

My code is yielding true every time, and I can't find the problem. I've researched other similar questions asked on the internet, but most of them are for finding the exact solution to a sudoku board or generating sudoku boards. I just need to see if a board is solvable or not. If you could please tell me where my code is wrong I'd really appreciate it.

I'm getting "true" every single time right now, no matter the test case...For this test case provided, the answer should yield false.

const test02 = [
  ['.', '8', '9', '.', '4', '.', '6', '.', '5'],
  ['.', '7', '.', '.', '.', '8', '.', '4', '1'],
  ['5', '6', '.', '9', '.', '.', '.', '.', '8'],
  ['.', '.', '.', '7', '.', '5', '.', '9', '.'],
  ['.', '9', '.', '4', '.', '1', '.', '5', '.'],
  ['.', '3', '.', '9', '.', '6', '.', '1', '.'],
  ['8', '.', '.', '.', '.', '.', '.', '.', '7'],
  ['.', '2', '.', '8', '.', '.', '.', '6', '.'],
  ['.', '.', '6', '.', '7', '.', '.', '8', '.']
];

function getCandidates(board, row, col) {
  const candidates = [];

  for (let chr = 1; chr <= 9; chr++) {
    let collision = false;
    for (let i = 0; i < 9; i++) {
      if (
        board[row][i] == chr ||
        board[i][col] == chr ||
        board[row - (row % 3) + Math.floor(i / 3)][
          col - (col % 3) + Math.floor(i / 3)
        ] == chr
      ) {
        collision = true;
        break;
      }
    }

    if (!collision) {
      candidates.push(chr);
    }
  }
  return candidates;
}

function sudokuSolve(board) {
  let row = -1;
  let col = -1;
  let candidates = [];

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] === '.') {
        newCandidates = getCandidates(board, r, c);
        if (
          candidates.length === 0 ||
          newCandidates.length < candidates.length
        ) {
          candidates = newCandidates;
          row = r;
          col = c;
        }
      }
    }
  }
  if (candidates.length === 0) {
    return true;
  } else {
    let solvable = false;
    candidates.forEach(val => {
      board[row][col] = val;
      if (sudokuSolve(board)) {
        solvable = true;
      } else {
        board[row][col] = '.';
      }
    });
    return solvable;
  }
}
console.log(
  sudokuSolve(test02)
);  

Juggler

I made you a snippet to make a runnable minimal reproducible example - I assumed sudokuSolve(test02) – Heymann

Add a few console.logs. For example console.log("# of candidates",candidates.length); – Heymann

Wouldn't be the problem, but in your collision check, you'd want to replace ONE of your Math.floor(i / 3) with i % 3 – Dewyeyed

Answer 1

The problem would be in your line :

if (candidates.length === 0) {
    return true;

You are not distinguishing between two cases for the candidates being empty - it could be :

a) The puzzle has been completely solved with no unknown "." squares remaining (in which case, yes, return true)

b) The puzzle has become unsolvable, and the remaining "." squares do not have any valid values

Since you are returning "true" for both of these, it will appear that everything is solved.

Try adding a boolean to detect if any "." squares remain, and use that instead in your 'if' condition :

let allSquaresFilled = true;
for (let r = 0; r < 9; r++) {
  for (let c = 0; c < 9; c++) {
    if (board[r][c] === '.') {
        allSquaresFilled = false;


if (allSquaresFilled) {
    return true;

Dewyeyed