469,300 Members | 2,352 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,300 developers. It's quick & easy.

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 1551
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

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

5 posts views Thread by sub1ime_uk | last post: by
5 posts views Thread by Stewart Gordon | last post: by
11 posts views Thread by ago | last post: by
12 posts views Thread by kalinga1234 | last post: by
reply views Thread by JosAH | last post: by
6 posts views Thread by blux | last post: by
21 posts views Thread by ningxin | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
1 post views Thread by Geralt96 | last post: by
reply views Thread by harlem98 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.