If someone can test this and find the problem that would be very helpful. The algorithm solves the puzzles but has some zeros in the solution which is not valid sudoku. I think the problem is if the number is possible in that cell then it assumes its correct.
export const initiate = (board) => {
const updatedBoard = board.map((i) =>
i.map((j) => (j === 0 ? (j = null) : j))
);
const validInput = validBoard(updatedBoard);
if (!validInput) {
return false;
}
return solve(updatedBoard);
};
const solve = (board) => {
if (isSolved(board)) {
return board;
}
const possibilities = findPossibilities(board);
const validBoards = keepValid(possibilities);
return searchForSolution(validBoards);
};
const searchForSolution = (boards) => {
if (boards.length < 1) {
return false;
}
const first = boards.shift();
const tryPath = solve(first);
if (tryPath) {
return tryPath;
}
return searchForSolution(boards);
};
const isSolved = (board) => {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] === null) {
return false;
}
}
}
return true;
};
const findPossibilities = (board) => {
let res = [];
const firstEmptySqr = findEmptySqr(board);
if (firstEmptySqr !== undefined) {
const y = firstEmptySqr[0];
const x = firstEmptySqr[1];
for (let i = 0; i <= 9; i++) {
const newBoard = [...board];
const row = [...newBoard[y]];
row[x] = i;
newBoard[y] = row;
res.push(newBoard);
}
}
return res;
};
const findEmptySqr = (board) => {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] === null) {
return [i, j];
}
}
}
};
const keepValid = (boards) => {
let res = [];
for (let i = 0; i < boards.length; i++) {
if (validBoard(boards[i])) {
res.push(boards[i]);
}
}
return res;
};
const validBoard = (board) => {
return rowsValid(board) && columnsValid(board) && boxesValid(board);
};
function rowsValid(board) {
for (let i = 0; i < 9; i++) {
let cur = [];
for (let j = 0; j < 9; j++) {
if (cur.includes(board[i][j])) {
return false;
} else if (board[i][j] !== null) {
cur.push(board[i][j]);
}
}
}
return true;
}
function columnsValid(board) {
for (let i = 0; i < 9; i++) {
let cur = [];
for (let j = 0; j < 9; j++) {
if (cur.includes(board[j][i])) {
return false;
} else if (board[j][i] !== null) {
cur.push(board[j][i]);
}
}
}
return true;
}
function boxesValid(board) {
const boxCoordinates = [
[0, 0],
[0, 1],
[0, 2],
[1, 0],
[1, 1],
[1, 2],
[2, 0],
[2, 1],
[2, 2],
];
for (let y = 0; y < 9; y += 3) {
for (let x = 0; x < 9; x += 3) {
let cur = [];
for (let i = 0; i < 9; i++) {
let coordinates = [...boxCoordinates[i]];
coordinates[0] += y;
coordinates[1] += x;
if (cur.includes(board[coordinates[0]][coordinates[1]])) {
return false;
} else if (board[coordinates[0]][coordinates[1]] !== null) {
cur.push(board[coordinates[0]][coordinates[1]]);
}
}
}
}
return true;
}
I was expecting this to solve the sudoku puzzle without returning zeros because in sudoku there are no zeros
In findPossibilities
you have a bug in the loop.
In the first iteration 0 is assigned to row[x]
, which is not what you want to happen. So change this line:
for (let i = 0; i <= 9; i++) {
to:
for (let i = 1; i <= 9; i++) {