Algorithm to determine if a sudoku puzzle is valid

5.24K viewsAlgorithmsalgorithms javascript puzzles sudoku valid
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
PuzzleMaster (anonymous) 0 Comments

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
0
Elucidase (anonymous) 0 Comments

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

Changed status to publish
Write your answer.

Categories