Skip to content

Instantly share code, notes, and snippets.

@EdgardoRodriguezSolano
Created January 1, 2020 02:22
Show Gist options
  • Save EdgardoRodriguezSolano/5dc90acdde9c3fde97360dd77f90577e to your computer and use it in GitHub Desktop.
Save EdgardoRodriguezSolano/5dc90acdde9c3fde97360dd77f90577e to your computer and use it in GitHub Desktop.
This is a sudoku solver. The initial state of the sudoku board is defined between lines 4-14. The program outputs all the existing solutions (if any) for a particular initial state.
// Leaving this here for reference https://es.wikipedia.org/wiki/Sudoku
console.log("Sudoku solver is running...");
// Here we can change the initial board configuration. The sudoku that we are trying to solve.
let sudoku = [
[0,0,8,0,7,0,0,0,9],
[0,0,2,0,0,3,0,0,0],
[6,3,0,0,0,0,0,0,0],
[0,5,3,0,0,4,2,7,0],
[0,0,0,0,0,2,3,0,0],
[0,0,0,0,0,5,9,6,4],
[0,8,6,5,0,0,4,0,0],
[0,0,7,0,2,0,0,5,0],
[0,9,5,8,4,6,0,2,0]
];
console.log("Original sudoku configuration \n", sudoku);
// Following is the convention I will be using to differentiate between the 3x3 "zones" inside the board
// NW N NE
// W C E
// SW S SE
let isAvailable = {
"NW": new Array(9).fill(true),
"N": new Array(9).fill(true),
"NE": new Array(9).fill(true),
"W": new Array(9).fill(true),
"C": new Array(9).fill(true),
"E": new Array(9).fill(true),
"SW": new Array(9).fill(true),
"S": new Array(9).fill(true),
"SE": new Array(9).fill(true)
};
getValidationZoneName = (row, col) => {
// Conditions for the zones.
// NW, i<3, j<3
// N, i<3, 2<j<6
// NE, i<3, 5<j<9
// ...and so on
if (row < 3 && col < 3) return "NW";
if (row < 3 && (2 < col) && (col < 6)) return "N";
if ((row < 3) && (5 < col) && (col < 9)) return "NE";
if ((2 <row) && (row < 6) && col < 3) return "W";
if ((2 <row) && (row < 6) && (2 < col) && (col < 6)) return "C";
if ((2 <row) && (row < 6) && (5 < col) && (col < 9)) return "E";
if ((5 <row) && (row < 9) && (col < 3)) return "SW";
if ((5 <row) && (row < 9) && (2 < col) && (col < 6)) return "S";
if ((5 <row) && (row < 9) && (5 < col) && (col < 9)) return "SE";
}
initializeZoneValidations = (sudoku) => {
for (row = 0; row < 9; row++) {
for (col = 0; col < 9; col++) {
if (sudoku[row][col] != 0) {
isAvailable[getValidationZoneName(row,col)][sudoku[row][col] - 1] = false; // There is a -1 offset. The flag for number 1 corresponds to the zero position in this vector.
}
}
}
}
initializeHorizontalValidations = (sudoku) => {
let horizontal = [];
for (row = 0; row < 9; row++) {
horizontal.push([]);
for (col = 0; col < 9; col++) {
if (sudoku[row][col] != 0) {
horizontal[row].push(sudoku[row][col]);
}
}
}
return horizontal;
}
initializeVerticalValidations = (sudoku) => {
let vertical = [];
for (col = 0; col < 9; col++) {
vertical.push([]);
for (row = 0; row < 9; row++) {
if (sudoku[row][col] != 0) {
vertical[col].push(sudoku[row][col]);
}
}
}
return vertical;
}
initializeZoneValidations(sudoku);
let horizontal = initializeHorizontalValidations(sudoku);
let vertical = initializeVerticalValidations(sudoku);
canBePlaced = (row, col, currentNumber) => {
if (!horizontal[row].includes(currentNumber) && !vertical[col].includes(currentNumber) &&
isAvailable[getValidationZoneName(row,col)][currentNumber - 1]) {
return true;
}
return false;
}
updateValidations = (row, col, currentNumber) => {
horizontal[row].push(currentNumber);
vertical[col].push(currentNumber);
isAvailable[getValidationZoneName(row,col)][currentNumber - 1] = false;
}
revertValidations = (row, col, currentNumber) => {
horizontal[row].pop();
vertical[col].pop();
isAvailable[getValidationZoneName(row,col)][currentNumber - 1] = true;
}
SudokuSolver = (row, col, currentBoard, currentNumber) => {
if (currentBoard[row][col] == 0) { // Not a fixed number
if (canBePlaced(row, col, currentNumber)) {
currentBoard[row][col] = currentNumber;
updateValidations(row, col, currentNumber);
if (row == 8 && col == 8) {
numberOfSolutions++;
console.log(`Solution # ${numberOfSolutions} \n`, currentBoard);
}
if (col < 8) {
SudokuSolver(row, col + 1, currentBoard, 1);
} else if (row < 8) {
SudokuSolver(row + 1, 0, currentBoard, 1);
}
revertValidations(row, col, currentNumber);
currentBoard[row][col] = 0;
}
if (currentNumber < 9) {
SudokuSolver(row, col, currentBoard, currentNumber + 1);
}
} else {
if (col < 8) {
SudokuSolver(row, col + 1, currentBoard, 1);
} else if (row < 8) {
SudokuSolver(row + 1, 0, currentBoard, 1);
}
}
}
let numberOfSolutions = 0;
SudokuSolver(0, 0, sudoku, 1); // Main call
if (numberOfSolutions == 0) {
}
switch (numberOfSolutions) {
case 0:
console.log("No solution for the initial sudoku configuration was found.");
break;
case 1:
console.log("An unique solution was found.");
break;
default:
console.log(`There are a total of ${numberOfSolutions} solutions possible.`);
}
// Now, in order to send the logic only and to apply withing my self-imposed deadline,
// I'm removing the input part ot the program and the sudoku will be modified when declaring it
// by code
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment