Created
January 1, 2020 02:22
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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