Sudoku solver with Javascript

Question

I tried t build a Sudoku Solver with Javascript. The code solves it indeed but stil there are some blank spots left. I use Javascript, backtracking and recursion.

In the first function i check i a number on a blank spot (0) is possible and in the second function i call the first one to check for empty spots and try to put a number between 1 and 9 in that spot

Can someone see what i am doing wrong?

const userInput = [
  [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],
];


function possible(y, x, n) {
  for (let i = 0; i <= 8; i++) {
    if (userInput[y][i] === n) {
      return false;
    }
  }
  for (let i = 0; i <= 8; i++) {
    if (userInput[i][x] === n) {
      return false;
    }
  }
  let xSquare = Math.floor(x / 3) * 3;
  let ySquare = Math.floor(y / 3) * 3;
  for (let i = 0; i <= 2; i++) {
    for (let j = 0; j <= 2; j++) {
      if (userInput[ySquare + i][xSquare + j] === n) {
        return false;
      }
    }
  }
  return true;
}


function solve() {
  for (let y = 0; y <= 8; y++) {
    for (let x = 0; x <= 8; x++) {
      if (userInput[y][x] === 0) {
        for (let n = 1; n <= 9; n++) {
          if (possible(y, x, n)) {
            userInput[y][x] = n;
            solve();
          }
        }
      }
    }
  }
}

Answer 1

You're writing a backtracking algorithm, but there's no backtracking here. The current algorithm assumes every guessed value will be perfect--if any aren't (which is guaranteed since the values are guessed sequentially from 1 to 9), no progress can be made.

To backtrack, you'll need to zero out cells that weren't able to be expanded to a solved state and return false to the parent state when all possibilities for the cell are exhausted.

Also, it's best for functions to take parameters and return values rather than mutating global state.

Applying these minimal modifications yields the following. There is still room for improvement; for example, the solve function has to "hunt" for the next open square repeatedly.

function possible(board, y, x, n) {
  for (let i = 0; i < 9; i++) {
    if (board[y][i] === n || board[i][x] === n) {
      return false;
    }
  }

  const xSquare = Math.floor(x / 3) * 3;
  const ySquare = Math.floor(y / 3) * 3;

  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (board[ySquare+i][xSquare+j] === n) {
        return false;
      }
    }
  }

  return true;
}

function solve(board) {
  for (let y = 0; y < 9; y++) {
    for (let x = 0; x < 9; x++) {
      if (board[y][x] === 0) {
        for (let n = 1; n <= 9; n++) {
          if (possible(board, y, x, n)) {
            board[y][x] = n;
            
            if (solve(board)) return board;
          }
        }
        
        board[y][x] = 0;
        return false;
      }
    }
  }
  
  return board;
}

const puzzle = [
  [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],
];

console.log(solve(puzzle).map(e => "" + e));