1 /**
  2  * Sudoku
  3  * @author Victor
  4  * @date 2013-7-10 上午8:47:44
  5  */
  6 public class Sudoku {
  7     
  8     public static void main(String[] args) {
  9         // TODO Auto-generated method stub
 10         String input = "....3..9....2....1.5.9..............1.2.8.4.6.8.5...2..75......4.1..6..3.....4.6.";
 11         System.out.println(input);
 12         String out = new Sudoku().sudoku(input);
 13         if(out == null) {
 14             System.out.println("failed.");
 15         } else {
 16             System.out.println(out);
 17         }
 18     }
 19 
 20     private final static int MAX = 9;
 21     private int[][] input(String in) {
 22         final int[][] matrix = new int[MAX][MAX];
 23         for (int i = 0; i < MAX; i++) {
 24             for (int j = 0; j < MAX; j++) {
 25                 char c = in.charAt(MAX * i + j);
 26                 if(c == '.') {
 27                     matrix[i][j] = 0;
 28                 } else {                    
 29                     matrix[i][j] = Integer.parseInt(String.valueOf(c));
 30                 }                
 31             }
 32         }
 33         return matrix;
 34     }
 35     
 36     private String output(final int[][] matrix) {
 37         StringBuilder out = new StringBuilder();
 38         for (int i = 0; i < MAX; i++) {
 39             for (int j = 0; j < MAX; j++) {
 40                 out.append(matrix[i][j]);        
 41             }
 42         }
 43         return out.toString();
 44     }
 45 
 46     private String sudoku(String input) {        
 47         // input matrix
 48         int[][] originalMatrix = input(input);
 49         int[][] detectMatrix = input(input);
 50         
 51         if(sudokuRecursive(originalMatrix, detectMatrix, 0)) {
 52             return output(detectMatrix);
 53         }
 54         
 55         return null;
 56     }
 57     
 58     /**
 59      * 递归求解
 60      * @author Victor
 61      * @date 2013-7-10 下午9:10:09
 62      * @param originalMatrix  原输入矩阵
 63      * @param detectMatrix   探测矩阵,存放每一个位置的探测结果
 64      * @param pos 当前探测的位置
 65      * @return boolean  是否成功
 66      */
 67     private boolean sudokuRecursive(int[][] originalMatrix, int[][] detectMatrix, int pos) {
 68         int x = pos / MAX;
 69         int y = pos % MAX;        
 70         if(pos == 81) {
 71             return true;
 72         }        
 73         if(originalMatrix[x][y] == 0) {
 74             for(int c = 1; c < MAX + 1; c++) {
 75                 if(isAllowed(x, y, c, detectMatrix)) {
 76                     detectMatrix[x][y] = c;
 77                     if(sudokuRecursive(originalMatrix, detectMatrix, pos + 1))
 78                         return true;
 79                 }
 80             }
 81             detectMatrix[x][y] = 0;
 82             return false;
 83         } else {
 84             detectMatrix[x][y] = originalMatrix[x][y];
 85             if(sudokuRecursive(originalMatrix, detectMatrix, pos + 1))
 86                 return true;
 87         }
 88         return false;
 89      }
 90     
 91     /**
 92      * Check在(x,y)位置是否可以放置candidate
 93      * @author Victor
 94      * @date 2013-7-8 下午7:20:00
 95      * @param x x坐标 0,1,2....8
 96      * @param y y坐标 0,1,2....8
 97      * @param candidate 候选数字
 98      * @param matrix 输入矩阵
 99      * @return boolean 是否允许放置该数字
100      */
101     private static boolean isAllowed(final int x, final int y, final int candidate, final int[][] matrix) {
102         return allowInRow(x, candidate, matrix) && allowInColumn(y, candidate, matrix) && allowInUnit(x, y, candidate, matrix);
103     }
104 
105     private static boolean allowInRow(final int x, final int candidate, final int[][] matrix) {
106         for(int y = 0; y < MAX; y++) {
107             // y is immutable
108             if(candidate == matrix[x][y])
109                 return false;
110         }
111         return true;
112     }
113 
114     private static boolean allowInColumn(final int y, final int candidate, final int[][] matrix) {
115         for(int x = 0; x < MAX; x++) {
116             // x is immutable
117             if(candidate == matrix[x][y])
118                 return false;
119         }
120         return true;
121     }
122 
123     private static boolean allowInUnit(final int x, final int y, final int candidate, final int[][] matrix) {
124         // 0,1,2 to 0; 3,4,5 to 1; 6,7,8 to 2
125         int xScale = x / 3;
126         int yScale = y / 3;
127         for(int m = xScale * 3; m < (xScale + 1) * 3; m++) {
128             for(int n = yScale * 3; n < (yScale + 1) * 3; n++) {
129                 // x is in [xScale * 3, (xScale + 1) * 3), y is in [yScale * 3, (yScale + 1) * 3)
130                 if(candidate == matrix[m][n])
131                     return false;
132             }
133         }
134         return true;
135     }
136 }