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
}
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
}