LeetCode 36 - Valid Sudoku


Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be partially filled, where empty cells are filled with the character '.'. Below is a partially filled sudoku which is valid.
Each row must have the numbers 1-9 occuring just once.
Each column must have the numbers 1-9 occuring just once.
And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.

  • With three passes
public boolean isValidSudoku(char[][] board) {
    HashSet<Character> set = new HashSet<Character>();
    // Check for each row
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.')
                continue;
            if (set.contains(board[i][j]))
                return false;
            set.add(board[i][j]);
        }
        set.clear();
    }
    // Check for each column
    for (int j = 0; j < 9; j++) {
        for (int i = 0; i < 9; i++) {
            if (board[i][j] == '.')
                continue;
            if (set.contains(board[i][j]))
                return false;
            set.add(board[i][j]);
        }
        set.clear();
    }
    // Check for each sub-grid
    for (int k = 0; k < 9; k++) {
        for (int i = k/3*3; i < k/3*3+3; i++) {
            for (int j = (k%3)*3; j < (k%3)*3+3; j++) {
                if (board[i][j] == '.')
                    continue;
                if (set.contains(board[i][j]))
                    return false;
                set.add(board[i][j]);
            }
        }
        set.clear();
    }
    return true;
}
X. https://www.programcreek.com/2014/05/leetcode-valid-sudoku-java/
public boolean isValidSudoku(char[][] board) {
 if (board == null || board.length != 9 || board[0].length != 9)
  return false;
 // check each column
 for (int i = 0; i < 9; i++) {
  boolean[] m = new boolean[9];
  for (int j = 0; j < 9; j++) {
   if (board[i][j] != '.') {
    if (m[(int) (board[i][j] - '1')]) {
     return false;
    }
    m[(int) (board[i][j] - '1')] = true;
   }
  }
 }
 
 //check each row
 for (int j = 0; j < 9; j++) {
  boolean[] m = new boolean[9];
  for (int i = 0; i < 9; i++) {
   if (board[i][j] != '.') {
    if (m[(int) (board[i][j] - '1')]) {
     return false;
    }
    m[(int) (board[i][j] - '1')] = true;
   }
  }
 }
 
 //check each 3*3 matrix
 for (int block = 0; block < 9; block++) {
  boolean[] m = new boolean[9];
  for (int i = block / 3 * 3; i < block / 3 * 3 + 3; i++) {
   for (int j = block % 3 * 3; j < block % 3 * 3 + 3; j++) {
    if (board[i][j] != '.') {
     if (m[(int) (board[i][j] - '1')]) {
      return false;
     }
     m[(int) (board[i][j] - '1')] = true;
    }
   }
  }
 }
 
 return true;
}
Code from http://xixiaogualu.blogspot.com/2013/09/leetcode-valid-sudoku.html
http://www.programcreek.com/2014/05/leetcode-valid-sudoku-java/

It used boolean[10], instead of set:




boolean[] checker=new boolean[10];




checker[c-'0']=true;




EPI Solution:
  • With one pass: space for speed
public boolean isValidSudoku(char[][] board) {
    // rowChecker[i][j]=true: j appears in row i
    boolean[][] rowChecker = new boolean[9][9];
    // columnChecker[i][j]=true: j appears in column i
    boolean[][] columnChecker = new boolean[9][9];
    // gridChecker[i][j]=true: j appears in grid i
    // numberring from left to right, then top to bottom
    boolean[][] gridChecker = new boolean[9][9];
    // One-pass scan in row-major manner
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.')
                continue;
            int val = board[i][j] - '1';
            // Check for the corresponding row, column, and grid at the same time
            if (rowChecker[i][val] || columnChecker[j][val] || gridChecker[i/3*3+j/3][val])
                return false;
            rowChecker[i][val] = columnChecker[j][val] = gridChecker[i/3*3+j/3][val] = true;
        }
    }
    return true;
}
https://www.cnblogs.com/grandyang/p/4421217.html
这道题让我们验证一个方阵是否为数独矩阵，判断标准是看各行各列是否有重复数字，以及每个小的3x3的小方阵里面是否有重复数字，如果都无重复，则当前矩阵是数独矩阵，但不代表待数独矩阵有解，只是单纯的判断当前未填完的矩阵是否是数独矩阵。那么根据数独矩阵的定义，我们在遍历每个数字的时候，就看看包含当前位置的行和列以及3x3小方阵中是否已经出现该数字，那么我们需要三个标志矩阵，分别记录各行，各列，各小方阵是否出现某个数字，其中行和列标志下标很好对应，就是小方阵的下标需要稍稍转换一下

X. https://leetcode.com/problems/valid-sudoku/discuss/15472/Short%2BSimple-Java-using-Strings
public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet();
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            char number = board[i][j];
            if (number != '.')
                if (!seen.add(number + " in row " + i) ||
                    !seen.add(number + " in column " + j) ||
                    !seen.add(number + " in block " + i/3 + "-" + j/3))
                    return false;
        }
    }
    return true;
}
X. https://blog.csdn.net/mine_song/article/details/70207326
依次检查每行，每列，每个子九宫格是否出现重复元素，如果出现返回false，否则返回true.

难点在于表示第i个九宫格每个格点的坐标。

观察行号规律：


第0个九宫格：000111222; 第1个九宫格：000111222; 第2个九宫格：000111222;

第3个九宫格：333444555; 第4个九宫格：333444555; 第5个九宫格：333444555;

第6个九宫格：666777888; 第7个九宫格：666777888; 第8个九宫格：666777888;

可见对于每三个九宫格行号增3；对于单个九宫格，每三个格点行号增1。

因此第i个九宫格的第j个格点的行号可表示为i/3*3+j/3（每个小九宫格j都是从0~9递增）

观察列号规律：


第0个九宫格：012012012; 第1个九宫格：345345345; 第2个九宫格：678678678;

第3个九宫格：012012012; 第4个九宫格：345345345; 第5个九宫格：678678678;

第6个九宫格：012012012; 第7个九宫格：345345345; 第8个九宫格：678678678;

可见对于下个九宫格列号增3，循环周期为3；对于单个九宫格，每个格点行号增1，周期也为3。

周期的数学表示就是取模运算mod。

因此第i个九宫格的第j个格点的列号可表示为i%3*3+j%3（每个小九宫格j都是从0~9递增）

部分填充的有效数独，不需要填充

细节分析题

（1）检查行

（2）检查列

（3）检查9个子宫格
  public boolean isValidSudoku(char[][] board) {
    for (int i = 0; i < 9; i++) {
      HashSet<Character> row = new HashSet<>();
      HashSet<Character> column = new HashSet<>();
      HashSet<Character> cube = new HashSet<>();
      for (int j = 0; j < 9; j++) {
        // 检查第i行，在横坐标位置
        if (board[i][j] != '.' && !row.add(board[i][j]))
          return false;
        // 检查第i列，在纵坐标位置
        if (board[j][i] != '.' && !column.add(board[j][i]))
          return false;
        // 行号+偏移量
        int RowIndex = 3 * (i / 3) + j / 3;
        // 列号+偏移量
        int ColIndex = 3 * (i % 3) + j % 3;
        // 每个小九宫格，总共9个
        if (board[RowIndex][ColIndex] != '.' && !cube.add(board[RowIndex][ColIndex]))
          return false;
      }
    }
    return true;

  }


https://leetcode.com/discuss/17990/sharing-my-easy-understand-java-solution-using-set

https://leetcode.com/discuss/27272/shared-my-concise-java-code
Just trying to explain how to think about % and /. These two operators can be helpful for matrix traversal problems.
For a block traversal, it goes the following way.
0,0, 0,1, 0,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.
1,0, 1,1, 1,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.
2,0, 2,1, 2,2; < --- 3 Horizontal Steps.
And so on... But, the j iterates from 0 to 9.
But we need to stop after 3 horizontal steps, and go down 1 step vertical.
Use % for horizontal traversal. Because % increments by 1 for each j : 0%3 = 0 , 1%3 = 1, 2%3 = 2, and resets back. So this covers horizontal traversal for each block by 3 steps.
Use / for vertical traversal. Because / increments by 1 after every 3 j: 0/3 = 0; 1/3 = 0; 2/3 =0; 3/3 = 1.
So far, for a given block, you can traverse the whole block using just j.
But because j is just 0 to 9, it will stay only first block. But to increment block, use i. To movehorizontally to next block, use % again : ColIndex = 3 * i%3 (Multiply by 3 so that the next block is after 3 columns. Ie 0,0 is start of first block, second block is 0,3 (not 0,1);
Similarly, to move to next block vertically, use / and multiply by 3 as explained above. Hope this helps.
public boolean isValidSudoku(char[][] board) {
    for(int i = 0; i<9; i++){
        HashSet<Character> rows = new HashSet<Character>();
        HashSet<Character> columns = new HashSet<Character>();
        HashSet<Character> cube = new HashSet<Character>();
        for (int j = 0; j < 9;j++){
            if(board[i][j]!='.' && !rows.add(board[i][j]))
                return false;
            if(board[j][i]!='.' && !columns.add(board[j][i]))
                return false;
            int RowIndex = 3*(i/3);
            int ColIndex = 3*(i%3);
            if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))
                return false;
        }
    }
    return true;
}
https://leetcode.com/discuss/64668/short-simple-java-using-strings
Collect the set of things we see, encoded as strings. For example:
  • '4' in row 7 is encoded as "(4)7".
  • '4' in column 7 is encoded as "7(4)".
  • '4' in the top-right block is encoded as "0(4)2".
Scream false if we ever fail to add something because it was already added (i.e., seen before).
public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet();
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            if (board[i][j] != '.') {
                String b = "(" + board[i][j] + ")";
                if (!seen.add(b + i) || !seen.add(j + b) || !seen.add(i/3 + b + j/3))
                    return false;
            }
        }
    }
    return true;
}
Just occurred to me that we can also make it really clear and self-explaining
public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet();
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            char number = board[i][j];
            if (number != '.')
                if (!seen.add(number + " in row " + i) ||
                    !seen.add(number + " in column " + j) ||
                    !seen.add(number + " in block " + i/3 + "-" + j/3))
                    return false;
        }
    }
    return true;
}
http://www.fusu.us/2013/07/verifying-sudoku-solution.html

public static boolean isValidSudoku(int[][] board, int order) {
long[] rows = new long[order * order];
long[] columns = new long[order * order];
long[][] boxes = new long[order][order];
int length = order * order;
for (int i = 0; i < length; i++) {
int boxI = i / 3;
for (int j = 0; j < length; j++) {
int boxJ = j / 3;
int value = board[i][j];
// consider unfinished solutions
if (value == 0) {
continue;
}
if ((rows[i] & 1 << (value - 1)) > 0) {
return false;
} else {
rows[i] = rows[i] | 1 << (value - 1);
}
if ((columns[i] & 1 << (value - 1)) > 0) {
return false;
} else {
columns[i] = columns[i] | 1 << (value - 1);
}
if ((boxes[boxI][boxJ] & 1 << (value - 1)) > 0) {
return false;
} else {
boxes[boxI][boxJ] =
boxes[boxI][boxJ] | 1 << (value - 1);
}
}
}
return true;
}
http://www.cnblogs.com/TenosDoIt/p/3800485.html
    bool isValidSudoku(vector<vector<char> > &board) {
        int rowValid[10] = {0};//用于判断某一行是否合法，对于行来说这个数组可以重复使用
        int columnValid[9][10] = {0};//用于判断某一列是否合法
        int subBoardValid[9][10] = {0};//用于判断某一个九宫格是否合法
        for(int i = 0; i < 9; i++)
        {
            memset(rowValid, 0, sizeof(rowValid));
            for(int j = 0; j < 9; j++)
                if(board[i][j] != '.')
                {
                    if(!checkValid(rowValid, board[i][j]-'0') ||
                       !checkValid(columnValid[j], board[i][j]-'0') ||
                       !checkValid(subBoardValid[i/3*3+j/3], board[i][j]-'0'))
                       return false;
                }
        }
        return true;
    }
    bool checkValid(int vec[], int val)
    {
        if(vec[val] == 1)return false;
        vec[val] = 1;
        return true;
    }
上面的算法中，在双重循环时，我们默认了第一重循环表示矩阵的行、第二重循环表示矩阵的列。可以换一种思路：
  • 在检测行是否合法时，i 表示矩阵的行，j 表示矩阵的列；
  • 检测列是否合法时，i 表示矩阵的列，j 表示矩阵的行；
  • 检测九宫格是否合法时，i 表示九宫格的标号，j 表示九宫格里的每个元素（只是我们需要根据i、j定位相应的元素到原来的矩阵：第 i 个九宫格里面的第 j 个元素在原矩阵的第 3*(i/3) + j/3 行，第 3*(i%3) + j%3）列，“/” 表示整数除法）
    bool isValidSudoku(vector<vector<char> > &board) {
        int rowValid[10] = {0};//用于判断某一行是否合法
        int columnValid[10] = {0};//用于判断某一列是否合法
        int subBoardValid[10] = {0};//用于判断某一个九宫格是否合法
        for(int i = 0; i < 9; i++)
        {
            memset(rowValid, 0, sizeof(rowValid));
            memset(columnValid, 0, sizeof(columnValid));
            memset(subBoardValid, 0, sizeof(subBoardValid));
            for(int j = 0; j < 9; j++)
            {
                    if(!checkValid(rowValid, board[i][j]-'0') ||
                       !checkValid(columnValid, board[j][i]-'0') ||
                       !checkValid(subBoardValid, board[3*(i/3) + j/3][3*(i%3) + j%3]-'0'))
                       return false;
            }
        }
        return true;
    }

http://stackoverflow.com/questions/5111434/sudoku-validity-check-algorithm-how-does-this-code-works
public static bool IsValid(int[] values)
{
    // bit field (set to zero => no values processed yet)
    int flag = 0;
    foreach (int value in values)
    {
        // value == 0 => reserved for still not filled cells, not to be processed
        if (value != 0)
        {
            // prepares the bit mask left-shifting 1 of value positions
            int bit = 1 << value; 
            // checks if the bit is already set, and if so the Sudoku is invalid
            if ((flag & bit) != 0)
                return false;
            // otherwise sets the bit ("value seen")
            flag |= bit;
        }
    }
    // if we didn't exit before, there are no problems with the given values
    return true;
}
http://tech-wonderland.net/blog/leetcode-valid-sudoku.html
Read full article from LeetCode - Valid Sudoku | Darren's Blog
at
Labels: , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts