471,895 Members | 2,147 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,895 software developers and data experts.

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

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
reply views Thread by zermasroor | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.