# Algorithm to determine if a sudoku puzzle is valid

3.90K views
0

Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. 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/

Changed status to publish

0

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;
}

Changed status to publish