471,895 Members | 2,147 Online

# sudoku

Hi,
i done a sudoku solving program ,and i got solution for easy sudoku, Can u explain any logic to find out medium and hard sudoku.
Nov 19 '07 #1
4 1620
r035198x
13,262 8TB
Hi,
i done a sudoku solving program ,and i got solution for easy sudoku, Can u explain any logic to find out medium and hard sudoku.
I hope you went through this article.
Nov 19 '07 #2
JosAH
11,448 Expert 8TB
I wrote that article and solver and I'm curious how it behaves on 'difficult' problems.
Please let us know the results you find.

kind regards,

Jos
Nov 19 '07 #3
I wrote that article and solver and I'm curious how it behaves on 'difficult' problems.
Please let us know the results you find.

kind regards,

Jos
Expand|Select|Wrap|Line Numbers
1.  package hitori;
2.
3. public class Sudoku {
4.
5.
6.     public final static int puzzle[][] = {
7.         {2, 0, 0, 7, 4, 0, 8, 0, 1},
8.         {8, 0, 0, 2, 9, 0, 5, 0, 6},
9.         {0, 7, 5, 0, 8, 0, 0, 0, 0},
10.         {0, 0, 0, 8, 2, 0, 6, 0, 0},
11.         {4, 0, 2, 0, 0, 0, 9, 0, 8},
12.         {0, 0, 3, 0, 6, 9, 0, 0, 0},
13.         {0, 0, 0, 0, 1, 0, 4, 6, 0},
14.         {3, 0, 1, 0, 7, 8, 0, 0, 9},
15.         {6, 0, 9, 0, 5, 4, 0, 0, 7}
16.     };
17.
18.
19.     static boolean possibilities[][][] = new boolean[9][9][9];
20.
21.
22.     public static void fillPossibilitiesMatrix() {
23.         for (int row =0; row <puzzle.length; row++) {
24.             for  (int column =0; column <puzzle.length; column++) {
25.                 for (int number = 0; number<puzzle.length; number++){
26.                        possibilities[row][column][number] = true;
27.                 }
28.             }
29.         }
30.     }
31.
32.     public static void resetPossibilitiesValue(int row, int column, int number) {
33.
34.                      resetRow( row, number);
35.                      resetColumn( column, number);
36.                      int rebox=getBox(row,column);
37.                      resetBox( rebox, number);
38.
39.
40.     }
41.
42.     /**
43.      * Looks into the possibilities matrix and if the cell can have only one
44.      * possible value, then returns the correct number from 1 to 9,
45.      * else returns -1
46.      */
47.     public static void getCellSolution(int row, int column) {
48.        int trues = 0,value = 0;
49.        for (int number = 0;number<9;number++) {
50.            if (possibilities[row][column][number]) {
51.                     trues++;
52.                     value = number +1;
53.            }
54.        }
55.        if (trues == 1) {
56.                     puzzle[row][column] = value;
57.                 }
58.        }
59.     /**
60.      * Prints the Sudoku as 9 rows of 9 columns each
61.      */
62.     public static void printSudoku() {
63.        for( int row=0; row<puzzle.length; row++) {
64.            for( int column=0; column<puzzle.length; column++) {
65.                     System.out.print(puzzle[row][column] + " ");
66.            }
67.             System.out.println(" ");
68.        }
69.     }
70.
71.     public static void resetRow(int rerow, int number) {
72.          for( int column=0; column<puzzle.length; column++) {
73.                     possibilities[rerow][column][number-1] = false;
74.                }
75.     }
76.
77.     public static void resetColumn(int recolumn, int number) {
78.           for(int row=0; row<puzzle.length; row++) {
79.                     possibilities[row][recolumn][number-1] = false;
80.           }
81.     }
82.
83.     public static void resetBox(int box, int number) {
84.       switch(box) {
85.             case 1: for ( int row = 0; row<3; row++) {
86.                       for (int column= 0; column<3; column++) {
87.                            possibilities[row][column][number-1] = false;
88.                       }
89.                     } break;
90.             case 2: for ( int row = 0; row<3; row++) {
91.                       for (int column= 3; column<6; column++) {
92.                           possibilities[row][column][number-1] = false;
93.                       }
94.                     } break;
95.             case 3: for ( int row = 0; row<3; row++) {
96.                       for (int column= 6; column<9; column++) {
97.                           possibilities[row][column][number-1] = false;
98.                       }
99.                     }  break;
100.             case 4: for ( int row = 3; row<6; row++) {
101.                       for (int column= 0; column<3; column++) {
102.                           possibilities[row][column][number-1] = false;
103.                       }
104.                     } break;
105.             case 5: for (int  row = 3; row<6; row++) {
106.                       for (int column= 3; column<6; column++) {
107.                           possibilities[row][column][number-1] = false;
108.                       }
109.                     } break;
110.             case 6: for ( int row = 3; row<6; row++) {
111.                       for (int column= 6; column<9; column++) {
112.                           possibilities[row][column][number-1] = false;
113.                       }
114.                     } break;
115.             case 7: for ( int row = 6; row<9; row++) {
116.                       for (int column= 0; column<3; column++) {
117.                           possibilities[row][column][number-1] = false;
118.                       }
119.                     } break;
120.             case 8: for ( int row = 6; row<9; row++) {
121.                       for (int column= 3; column<6; column++) {
122.                           possibilities[row][column][number-1] = false;
123.                       }
124.                     } break;
125.             case 9: for ( int row = 6; row<9; row++) {
126.                       for (int column= 6; column<9; column++) {
127.                           possibilities[row][column][number-1] = false;
128.                       }
129.                     } break;
130.       }
131.     }
132.
133.     public static int checkSudoku() {
134.         int count = 0;
135.         for(int row = 0; row< 9; row++) {
136.             for ( int column = 0; column<9; column++) {
137.                if (puzzle[row][column] != 0) {
138.                   count++;
139.                }
140.             }
141.         }
142.         return count;
143.     }
144.      static int getBox(int row, int column) {
145.         int box = 0;
146.         box= ( 3*row/3)+(column/3) +1;
147.         return box;
148.      }
149.
150.
151.     public static void main(String argv[]) {
152.         int row,column,number;
153.         fillPossibilitiesMatrix();
154.        while (checkSudoku() < 81) {
155.          for ( row=0; row<puzzle.length; row++) {
156.            for ( column=0; column<puzzle.length;column++)  {
157.              number =  puzzle[row][column];
158.              if(number != 0) {
159.                  resetPossibilitiesValue (row,column,number);
160.              }
161.              else {
162.                  getCellSolution( row, column);
163.              }
164.            }
165.          }
166.         }
167.        printSudoku();
168.     }
169.     }
Nov 20 '07 #4
JosAH
11,448 Expert 8TB
Hi, did your program solve that puzzle? The solver described in that article solved
it instantaneously (I didn't time it though).

kind regards,

Jos
Nov 20 '07 #5