package com.fishercoder.solutions;

/**
 * Write a program to solve a Sudoku puzzle by filling the empty cells.
 * Empty cells are indicated by the character '.'.
 * You may assume that there will be only one unique solution.
  * A sudoku puzzle...
 * ...and its solution numbers marked in red.
 */
public class _37 {

    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        //try 1 to 9
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;

                            if (solve(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';//recover it to be '.'
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.' && board[i][col] == c) {
                return false;//check row
            }
            if (board[row][i] != '.' && board[row][i] == c) {
                return false;//check column
            }
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
                return false; //check 3*3 block
            }
        }
        return true;
    }

}

@@ -33,16 +33,40 @@
 s;%0A%0A/**%0A
+ * 37. Sudoku Solver%0A *%0A
  * Write
@@ -248,100 +248,71 @@
 n.%0A 
- * A sudoku puzzle...%0A * ...and its solution numbers marked in red.%0A */%0Apublic class _37 %7B%0A%0A
+*/%0Apublic class _37 %7B%0A%0A    public static class Solution1 %7B%0A    
     
@@ -353,32 +353,36 @@
 oard) %7B%0A        
+  
+  
 if (board == nul
@@ -415,24 +415,28 @@
             
+    
 return;%0A    
@@ -431,34 +431,42 @@
 return;%0A        
+   
+ 
 %7D%0A
+    
         solve(bo
@@ -471,27 +471,35 @@
 board);%0A    
+   
+ 
 %7D%0A%0A
+    
     private 
@@ -530,32 +530,36 @@
 oard) %7B%0A        
+   
+ 
 for (int i = 0; 
@@ -575,32 +575,36 @@
 .length; i++) %7B%0A
+    
             for 
@@ -651,32 +651,36 @@
                 
+   
+ 
 if (board%5Bi%5D%5Bj%5D 
@@ -685,24 +685,28 @@
 %5D == '.') %7B%0A
+    
             
@@ -745,24 +745,28 @@
 '9'; c++) %7B%0A
+    
             
@@ -810,24 +810,28 @@
             
+    
 if (isValid(
@@ -845,24 +845,28 @@
 i, j, c)) %7B%0A
+    
             
@@ -923,24 +923,28 @@
             
+    
 if (solve(bo
@@ -947,24 +947,28 @@
 e(board)) %7B%0A
+    
             
@@ -1028,16 +1028,20 @@
         
+    
 %7D else %7B
@@ -1041,16 +1041,20 @@
  else %7B%0A
+    
         
@@ -1138,34 +1138,42 @@
                 
-%7D%0A
+    %7D%0A    
                 
@@ -1194,34 +1194,42 @@
                 
+ 
-%7D%0A
+   %7D%0A    
                 
@@ -1254,34 +1254,42 @@
                 
+ 
-%7D%0A
+   %7D%0A    
             %7D%0A  
@@ -1286,34 +1286,42 @@
       %7D%0A        
+ 
-%7D%0A
+   %7D%0A    
         return t
@@ -1325,27 +1325,35 @@
 n true;%0A    
+ 
-%7D%0A%0A
+   %7D%0A%0A    
     private 
@@ -1412,32 +1412,36 @@
 ar c) %7B%0A        
+  
+  
 for (int i = 0; 
@@ -1446,32 +1446,36 @@
 ; i %3C 9; i++) %7B%0A
+    
             if (
@@ -1528,32 +1528,36 @@
                 
+  
+  
 return false;//c
@@ -1569,34 +1569,40 @@
 row%0A            
-%7D%0A
+    %7D%0A  
             if (
@@ -1589,32 +1589,34 @@
 %7D%0A              
+  
 if (board%5Brow%5D%5Bi
@@ -1657,32 +1657,36 @@
                 
+    
 return false;//c
@@ -1701,34 +1701,42 @@
 umn%0A            
+  
-%7D%0A
+  %7D%0A    
             if (
@@ -1865,32 +1865,36 @@
                 
+    
 return false; //
@@ -1913,32 +1913,36 @@
 ock%0A            
+    
 %7D%0A        %7D%0A    
@@ -1927,32 +1927,36 @@
       %7D%0A        
+ 
+   
 %7D%0A        return
@@ -1941,32 +1941,36 @@
       %7D%0A        
+ 
+   
 return true;%0A   
@@ -1962,21 +1962,31 @@
 eturn true;%0A
+        %7D%0A
     %7D%0A%0A%7D%0A

refactor 37