Valid Sudoku

Question

  1. Determine whether a Sudoku is valid.
  3. The Sudoku board could be partially filled,
  4. where empty cells are filled with the character ..
  6. Example
  7. The following partially filed sudoku is valid.

valid-sudoku.png

  1. Valid Sudoku
  3. Note
  4. A valid Sudoku board (partially filled) is not necessarily solvable.
  5. Only the filled cells need to be validated.
  6. Clarification
  7. What is Sudoku?
  9. http://sudoku.com.au/TheRules.aspx
  10. https://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8
  11. https://en.wikipedia.org/wiki/Sudoku
  12. http://baike.baidu.com/subview/961/10842669.htm

題解

看懂數獨的含義就好了，分為三點考慮，一是每行無重複數字；二是每列無重複數字；三是小的九宮格中無重複數字。

Java

  1. class Solution {
  2.     /**
  3.       * @param board: the board
  4.         @return: wether the Sudoku is valid
  5.       */
  6.     public boolean isValidSudoku(char[][] board) {
  7.         if (board == null || board.length == 0) return false;
  9.         // check row
  10.         for (int i = 0; i < 9; i++) {
  11.             boolean[] numUsed = new boolean[9];
  12.             for (int j = 0; j < 9; j++) {
  13.                 if (isDuplicate(board[i][j], numUsed)) {
  14.                     return false;
  15.                 }
  16.             }
  17.         }
  19.         // check column
  20.         for (int i = 0; i < 9; i++) {
  21.             boolean[] numUsed = new boolean[9];
  22.             for (int j = 0; j < 9; j++) {
  23.                 if (isDuplicate(board[j][i], numUsed)) {
  24.                     return false;
  25.                 }
  26.             }
  27.         }
  29.         // check sub box
  30.         for (int i = 0; i < 9; i = i + 3) {
  31.             for (int j = 0; j < 9; j = j + 3) {
  32.                 if (!isValidBox(board, i, j)) {
  33.                     return false;
  34.                 }
  35.             }
  36.         }
  38.         return true;
  39.     }
  41.     private boolean isValidBox(char[][] box, int x, int y) {
  42.         boolean[] numUsed = new boolean[9];
  43.         for (int i = x; i < x + 3; i++) {
  44.             for (int j = y; j < y + 3; j++) {
  45.                 if (isDuplicate(box[i][j], numUsed)) {
  46.                     return false;
  47.                 }
  48.             }
  49.         }
  50.         return true;
  51.     }
  53.     private boolean isDuplicate(char c, boolean[] numUsed) {
  54.         if (c == '.') {
  55.             return false;
  56.         } else if (numUsed[c - '1']) {
  57.             return true;
  58.         } else {
  59.             numUsed[c - '1'] = true;
  60.             return false;
  61.         }
  62.     }
  63. }

C++

  1. class Solution {
  2. public:
  3.     bool isValidBlock(vector<int>& v){
  4.         bool ans = true;
  5.         for(int i = 0; i < v.size(); i++){
  6.             if(v[i] > 1)
  7.                 ans = false;
  8.             v[i] = 0;
  9.         }
  10.         return ans;
  11.     }
  12.     bool isValidSudoku(vector<vector<char>>& board) {
  13.         vector<int> num(9, 0);
  15.         //row
  16.         for(int i=0; i<9; i++){
  17.             for(int j=0; j<9; j++){
  18.                 char n = board[i][j];
  19.                 if('1' <= n and n <= '9')
  20.                     num[n - '1'] ++;
  21.             }
  23.             if(!isValidBlock(num))
  24.                 return false;
  25.         }
  27.         //col
  29.         for(int j=0; j<9; j++){
  30.             for(int i=0; i<9; i++){
  31.                 char n = board[i][j];
  32.                 if('1' <= n and n <= '9')
  33.                     num[n - '1']++;
  34.             }
  35.             if(!isValidBlock(num))
  36.                 return false;
  37.         }
  39.         //block
  41.         for(int row = 0; row < 3; row++){
  42.             for(int col = 0; col < 3; col++){
  43.                 for(int i = 0; i < 3; i++){
  44.                     for(int j = 0; j < 3; j++){
  45.                         char n = board[3*row +i][3*col+j];
  46.                         if('1' <= n and  n <= '9')
  47.                             num[n - '1']++;
  48.                     }
  49.                 }
  50.                 if(!isValidBlock(num))
  51.                     return false;
  52.             }
  53.         }
  54.         return true;
  55.     }
  56. };

源碼分析

首先實現兩個小的子功能模塊判斷是否有重複和小的九宮格是否重複。

複雜度分析

略

Reference

  • Soulmachine 的 leetcode 題解