# Valid Sudoku ### Source - leetcode: [Valid Sudoku | LeetCode OJ](https://leetcode.com/problems/valid-sudoku/) - lintcode: [(389) Valid Sudoku](http://www.lintcode.com/en/problem/valid-sudoku/) ~~~ Determine whether a Sudoku is valid. The Sudoku board could be partially filled, where empty cells are filled with the character .. Example The following partially filed sudoku is valid. ~~~  ~~~ Valid Sudoku Note A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated. Clarification What is Sudoku? http://sudoku.com.au/TheRules.aspx https://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8 https://en.wikipedia.org/wiki/Sudoku http://baike.baidu.com/subview/961/10842669.htm ~~~ ### 題解 看懂數獨的含義就好了，分為三點考慮，一是每行無重復數字；二是每列無重復數字；三是小的九宮格中無重復數字。 ### Java ~~~ class Solution { /** * @param board: the board @return: wether the Sudoku is valid */ public boolean isValidSudoku(char[][] board) { if (board == null || board.length == 0) return false; // check row for (int i = 0; i < 9; i++) { boolean[] numUsed = new boolean[9]; for (int j = 0; j < 9; j++) { if (isDuplicate(board[i][j], numUsed)) { return false; } } } // check column for (int i = 0; i < 9; i++) { boolean[] numUsed = new boolean[9]; for (int j = 0; j < 9; j++) { if (isDuplicate(board[j][i], numUsed)) { return false; } } } // check sub box for (int i = 0; i < 9; i = i + 3) { for (int j = 0; j < 9; j = j + 3) { if (!isValidBox(board, i, j)) { return false; } } } return true; } private boolean isValidBox(char[][] box, int x, int y) { boolean[] numUsed = new boolean[9]; for (int i = x; i < x + 3; i++) { for (int j = y; j < y + 3; j++) { if (isDuplicate(box[i][j], numUsed)) { return false; } } } return true; } private boolean isDuplicate(char c, boolean[] numUsed) { if (c == '.') { return false; } else if (numUsed[c - '1']) { return true; } else { numUsed[c - '1'] = true; return false; } } } ~~~ ### 源碼分析 首先實現兩個小的子功能模塊判斷是否有重復和小的九宮格是否重復。 ### 復雜度分析 略 ### Reference - Soulmachine 的 leetcode 題解