1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Valid Sudoku
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/valid-sudoku/
7+ Notes:
8+ Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules (http://sudoku.com.au/TheRules.aspx).
9+ The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
10+
11+ Solution: 1. Traverse the Sudoku only once.
12+ 2. Bit manipulation. Use only one bit to represent a number. Space: sizeof(int) * (1+9+9).
13+ */
14+ public class Solution {
15+ public boolean isValidSudoku (char [][]board ) {
16+ boolean []used =new boolean [9 ];
17+
18+ for (int i =0 ;i <9 ;i ++){
19+ Arrays .fill (used ,false );
20+ for (int j =0 ;j <9 ;j ++){
21+ if (check (board [i ][j ],used )==false )return false ;
22+ }
23+ Arrays .fill (used ,false );
24+ for (int j =0 ;j <9 ;j ++){
25+ if (check (board [j ][i ],used )==false )return false ;
26+ }
27+ }
28+
29+ for (int r =0 ;r <3 ;r ++){
30+ for (int c =0 ;c <3 ;c ++){
31+ Arrays .fill (used ,false );
32+ for (int i =r *3 ;i <r *3 +3 ;i ++){
33+ for (int j =c *3 ;j <c *3 +3 ;j ++){
34+ if (check (board [i ][j ],used )==false )return false ;
35+ }
36+ }
37+ }
38+ }
39+ return true ;
40+ }
41+ boolean check (char ch ,boolean []used ){
42+ if (ch =='.' )return true ;
43+ if (used [ch -'1' ])return false ;
44+ used [ch -'1' ]=true ;
45+ return true ;
46+ }
47+ }
