Home > front end >  recursive backtracking algorithm that counts all solutions
recursive backtracking algorithm that counts all solutions

Time:03-24

I'm building a sudoku generator-solver app and currently finishing the hiding algorithm for useless cells.

I have a working backtracking algorithm that returns true when the solution is found, but I need to check if there're any other solutions to prevent a wrong board from creating.

findEmpty function finds the next empty cell inside a sudoku board. isValid function checks if the parameter passed fits in a current cell. Provided code returns true if the board is solved. It does overwrite the passed variable, so to access a solved board I call the variable passed.

If there's at least one extra solution, the function must return false. If the board cannot be solved, the function must return false. If there's a solution(only 1), return true

function backTrackSolve(board)
  {
      let find = findEmpty(board)
      if (find[0] == -1)
          return true
      
      let row = find[0]
      let col = find[1]
  
  
      for (let i = 1; i < 10; i  )
      {
  
          if (isValid(board, { row,col }, i))
          {
              board[row][col] = i
              if (backTrackSolve(board)){
                    return true
              }
  
            }
              board[row][col] = 0
      }
  
      return false
  
  }

CodePudding user response:

    function backTrackSolve(board)
      {
          let find = findEmpty(board)
          if (find[0] == -1){
              //count stuff here
              return false;
          }
          let row = find[0]
          let col = find[1]
      
      
          for (let i = 1; i < 10; i  )
          {
      
              if (isValid(board, { row,col }, i))
              {
                  board[row][col] = i
                  if (backTrackSolve(board)){
                        return true
                  }
      
                }
                  board[row][col] = 0
          }
      
          return false
      
     }
  • Related