Algorithm to determine if a sudoku puzzle is valid
Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the 9 3×3 sub-boxes of the grid must contain the digits 1-9 without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
Example 1:
Input:
[
[“5″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”],
[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”],
[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”],
[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″],
[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″],
[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″],
[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”],
[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″],
[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]
]
Output: true
Example 2:
Input:
[
[“8″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”],
[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”],
[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”],
[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″],
[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″],
[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″],
[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”],
[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″],
[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8’s in the top left 3×3 sub-box, it is invalid.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
- The given board contain only digits 1-9 and the character ‘.’.
- The given board size is always 9×9.
Posted from https://forum.golibrary.co/question/algorithm-determine-sudoku-puzzle-valid/
Here is another cryptic but short solution in javascript
var isValidSudoku = function(board) { for (let i = 0; i < 9; i++) { let row = new Set(), col = new Set(), sqr = new Set(); for (let j = 0; j < 9; j++) { let rowc = board[i][j]; let colc = board[j][i]; let sqrc = board[Math.floor(i / 3) * 3 + Math.floor(j / 3)][(i % 3) * 3 + j % 3]; if (row.has(rowc) || col.has(colc) || sqr.has(sqrc)) return false; if (rowc !== ".") row.add(rowc); if (colc !== ".") col.add(colc); if (sqrc !== ".") sqr.add(sqrc); } } return true; };
Below long but self explanatory algorithm in javascript !!
A sudoku is said to be valid if
- If all boxes (3×3 grids) contain no duplicates and thus unique numbers between 1-9
- All rows contain no duplicates and thus unique numbers between 1-9
- All columns contain no duplicates and thus unique numbers between 1-9
Checking the same conditions below in the code:-
/** * @param {character[][]} board * @return {boolean} */ var isValidSudoku = function(board) { var isValid = false; var cols = []; var rowItemRepeat = false; var colItemRepeat = false; var boxItemRepeat = false; var SUDOKU_LENGTH = board.length; var BOX_LENGTH = parseInt(Math.sqrt(SUDOKU_LENGTH)); for (var i = 0; i < board.length; i++) { rowItemRepeat = rowItemRepeat || checkRows(board[i]); var box = getBox(board, parseInt(i / BOX_LENGTH) * BOX_LENGTH, i*BOX_LENGTH % SUDOKU_LENGTH); boxItemRepeat = boxItemRepeat || hasDuplicates(box); cols[i] = []; for (var j = 0; j < board.length; j++) { if (board[j][i] !== '.') { cols[i].push(board[j][i]) } } colItemRepeat = colItemRepeat || hasDuplicates(cols[i]); } return !(rowItemRepeat || colItemRepeat || boxItemRepeat); }; var getBox = function(board, x, y) { var box = []; for (var a = x; a < x+3; a++) { for (var b = y; b < y+3; b++) { if (board[a][b] !== '.') { box.push(board[a][b]); } } } return box; } var checkRows = function(row) { var rowArr = []; var hasRepeat = false; for (var t = 0; t < row.length; t++) { hasRepeat = false; if (row[t] !== '.') { rowArr.push(row[t]); } } hasRepeat = hasRepeat || hasDuplicates(rowArr); return hasRepeat; } var hasDuplicates = function(array) { return (new Set(array)).size !== array.length; }