Algorithm to determine if a sudoku puzzle is valid

3.43K 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
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
You are viewing 1 out of 2 answers, click here to view all answers.
Write your answer.

Categories