Skip to content

Instantly share code, notes, and snippets.

@micmmakarov
Last active February 8, 2017 19:00
Show Gist options
  • Save micmmakarov/cb0bc71938321e2935022ccc7e763977 to your computer and use it in GitHub Desktop.
Save micmmakarov/cb0bc71938321e2935022ccc7e763977 to your computer and use it in GitHub Desktop.
Fast Sudoku validator in Javascript via array addresses
/*
Fast JS Sudoku validator implemented in Javascript via array addresses.
Check whether a 9x9 sudoku board is valid.
Sudoku is a game played on a 9x9 grid. The object of the game is to fill in every square on the grid with a number, 1-9, so that:
Every row contains the numbers 1-9
Every column contains the numbers 1-9
Each of the 9 3x3 sub grids contains the numbers 1-9
We are going to build a validator that will look at a 9x9 board, and decide if the player has made any mistakes so far.
(By entering duplicate 1-9 in any of row / column / section). However, will will not fail a board if it is still incomplete,
which is indicated by a zero in a square, as long as there are currently no duplicates.
*/
const sChecker = function(board) {
// Validates the board
if (board.length !== 9) {return false;}
const boardWidth = board.length;
const smallSquareSize = Math.sqrt(boardWidth)
const boardSize = board.length ** 2;
const boardArray = new Array(3 * boardSize + board.length);
for (let y = 0; y < board.length; y++) {
if (board[y].length !== 9) { return false }; // validates the board, this way is faster
for (let x = 0; x < board.length; x++) {
if (board[y][x] !== 0) {
let addresCol = x * boardWidth + board[y][x];
let addresRow = boardSize + y * boardWidth + board[y][x];
let addressSquare = boardSize * 2 + (Math.floor((y + 1) / smallSquareSize - 0.1) * smallSquareSize + Math.floor((x + 1) / smallSquareSize - 0.1)) * boardWidth + board[y][x];
if (boardArray[addressSquare] !== undefined || boardArray[addresCol] !== undefined || boardArray[addresRow] !== undefined || board[y][x] > boardWidth || board[y][x] < 0) {
return false;
} else {
boardArray[addresCol] = true;
boardArray[addresRow] = true;
boardArray[addressSquare] = true;
}
}
}
}
return true;
}
const passingSudokus = [
// Normal
[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]
],
// With 0s
[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 0, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 0, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 0, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]
]
];
const failingSudokus = [
// Wrong number '9'
[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 9, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]
],
// Wrong size
[
[5, 3, 4, 6, 7, 8, 9, 1, 2, 1],
[6, 7, 2, 1, 9, 5, 3, 4, 8, 2],
[1, 9, 8, 3, 4, 9, 5, 6, 7, 3],
[8, 5, 9, 7, 6, 1, 4, 2, 3, 5],
[4, 2, 6, 8, 5, 3, 7, 9, 1, 6],
[7, 1, 3, 9, 2, 4, 8, 5, 6, 8],
[9, 6, 1, 5, 3, 7, 2, 8, 4, 7],
[2, 8, 7, 4, 1, 9, 6, 3, 5, 7],
[2, 8, 7, 4, 1, 9, 6, 3, 5, 3],
[3, 4, 5, 2, 8, 6, 1, 7, 9, 1]
],
// Negative number
[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 9, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, -7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]
],
// wrong one
[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 3],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]
],
// another wrong one
[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 5, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 3, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 1, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]
]
];
console.log('Tests:');
passingSudokus.forEach(s => {
console.log(sChecker(s) === true);
});
failingSudokus.forEach(s => {
console.log(sChecker(s) === false);
});
console.time('10000 times');
for (let i = 0; i < 10000; i++) {
sChecker(passingSudokus[0]);
}
console.timeEnd('10000 times')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment