Is it possible to check whether a sudoku is solvable or not. I recently tried leetcode-36. But it only checks if the sudoku was valid, but i want to check for its solvability.
I designed a algorithm using backtracking, it checks for its validity and then solves the sudoku. For example if I gave sudoku that is unsolvable but is valid, it would check all 9^81 possibilities and then conclude it is not solvable. 9^81 is a huge number and my taking lots of time to give the result that sudoku is unsolvable.
For example check this sudoku, which is valid but unsolvable.
I want to know whether there is any algorithm that checks for sudoku to be solvable, or any such optimizations in backtracking that can be made to solve this issue.
i tried this code in js (I am designing a website for sudoku game)
function isSafe(matrix, row, col, num) {
for (let x = 0; x < 9; x++) {
if (matrix[row][x].value === num || matrix[x][col].value === num ||
matrix[3 * Math.floor(row / 3) + Math.floor(x / 3)][3 * Math.floor(col / 3) + x % 3].value === num) {
return false;
}
}
return true;
}
function solveSudoku(matrix) {
let empty = findEmptyLocation(matrix);
if (!empty) {
return true;
}
let row = empty[0];
let col = empty[1];
for (let num = 1; num <= 9; num++) {
if (isSafe(matrix, row, col, num)) {
matrix[row][col].value = num;
if (solveSudoku(matrix)) {
return true;
}
matrix[row][col].value = 0;
}
}
return false;
}
function findEmptyLocation(matrix) {
for (let row = 0; row < 9; row++) {
for (let col = 0; col < 9; col++) {
if (matrix[row][col].value === 0) {
return [row, col];
}
}
}
return null;
}