473,547 Members | 2,290 Online

# sudoku

2 New Member
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 1776
r035198x
13,262 MVP
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 #2
JosAH
11,448 Recognized Expert MVP
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
hashimtk
2 New Member
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 Recognized Expert MVP
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