By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
462,871 Members | 649 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 462,871 IT Pros & Developers. It's quick & easy.

sudoku

P: 2
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
Share this Question
Share on Google+
4 Replies

10K+
P: 13,262
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

Expert 10K+
P: 11,448
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

P: 2
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

Expert 10K+
P: 11,448
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.