1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Sudoku generation algorithm in JAVA : Any suggestions for improvement?

Discussion in 'Java' started by ManzZup, Jan 25, 2012.

  1. ManzZup

    ManzZup New Member

    Joined:
    May 9, 2009
    Messages:
    278
    Likes Received:
    43
    Trophy Points:
    0
    Occupation:
    Production Manager:Software @ ZONTEK
    Location:
    Sri Lanka
    Home Page:
    Hey guys,

    it's just this Sudoku (I'm sure many of you know what it is :) ) algo i developed and I'm pretty sure that my backtracking and bruteforcing method arent the best approach for is. So im posting th code, of course it is working, you are free to use and develope this code and if you do any improvement please let me know

    At the moment the average time taken by the script to generate a completely random puzzle is apx: 18 milliseconds

    See at work (though a small flash based game ) : http://zontek.zzl.org/zg/sudoku

    Code:
    import java.util.*;
    import java.util.Date;
    
    /*
    @author: manzzup
    @contact: facebook.com/manzzup
    @code at work: http://zontek.zzl.org/zg/sudoku
    #Please do let me know about any improvements via manzzup@gmail.com or above 
    */
    class Sudoku{
      final static int no = 9;
      static ArrayList cols[];
      static ArrayList rows[];
      static ArrayList boxes[];
      static int board[] = new int[1+(no*no)];
      
    	public static void main(String... args){
        System.out.println("###### Sudoku generation basic algorithm by ManZzup ######");
        resetBoard();
        Date d1 = new Date();
        generate(1);
        Date d2 = new Date();
        System.out.println("Time for generation : " + (d2.getTime() - d1.getTime()) + " milis");
    	System.out.println();
        printAry(board);
        
       
        
    	}
    	
    	static int getBox(int row,int col){
        if(row <=3){
          if(col <=3){
            return 1;
          }else if(col <=6){
            return 2;
          }else{
            return 3;
          }
        }else if(row <=6){
          if(col <=3){
            return 4;
          }else if(col <=6){
            return 5;
          }else{
            return 6;
          }
        }else if(row <= 9){
          if(col <=3){
            return 7;
          }else if(col <=6){
            return 8;
          }else{
            return 9;
          }
        }
        return 0;
    	}
    	
    	static boolean generate(int n){
            ArrayList<Integer> pool = new ArrayList<Integer>();
            int col = n%no;
            if(col==0) col=no;
            int row = (int)( Math.ceil(n/(double)no) );
            int box = getBox(row,col);
            //System.out.println(" cell " + n);
            //System.out.println(n + " " + row + " " + col);
            for(int i=1;i<=no;i++){
                if( (rows[row].contains(i) && cols[col].contains(i)) && boxes[box].contains(i)){
                      //System.out.print(i + " ");
                      pool.add(i);
                  }
            }
            //System.out.println();
            int ran;
            Integer sel=0;
            boolean ok = false;
            if(pool.size()==0) return false;
            while(!ok){
                //System.out.println("loop in cell : " + n);
                if(pool.size()==0){
                    //System.out.println("wrong +" + n);
                    return false;
                }else{
                    ran = (int)( Math.ceil(Math.random()*(pool.size()-1)) );
                    sel = pool.get(ran);
                    //System.out.println(sel);
                    board[n] = sel;
                    
                    rows[row].remove((Integer)sel);
                    cols[col].remove((Integer)sel);
                    boxes[box].remove((Integer)sel);
                    pool.remove(sel);
                    
                    if(n==(no*no)){
                      return true;
                    }else{
                      ok = generate(n+1);
                      if(!ok){
                          //System.out.println("not okay in " + n);
                          rows[row].add(sel);
                          cols[col].add(sel);
                          boxes[box].add(sel);
                      }
                    }
                }
            }
            
            return true;
    	}
    	
      static void resetBoard(){
        cols = new ArrayList[no+1];
        rows = new ArrayList[no+1];
        boxes = new ArrayList[no+1];
        
        for(int i=1;i<=no;i++){
          ArrayList<Integer> ary = new ArrayList<Integer>();
          ArrayList<Integer> ary2 = new ArrayList<Integer>();
          ArrayList<Integer> ary3 = new ArrayList<Integer>();
          for(int j=0;j<=no;j++){
              ary.add(j);
              ary2.add(j);
              ary3.add(j);
          }
          cols[i] = ary;
          rows[i] = ary2;
          boxes[i] = ary3;
        }
         
      }
    	static void printAry(int[] ary){
    		int root = (int)Math.sqrt(no);
    		for(int i=1;i<ary.length;i++){
    			System.out.printf("%2d",ary[i]);
    			if(i%root==0) System.out.print("  ");
    			if(i%no==0) System.out.println();
    			if(i%(no*root)==0) System.out.println();
    		}
    	}
    	static void printAryList(ArrayList ary){
        for(int i=1;i<=no;i++){
          System.out.println(ary.get(i));
        }
    	}
    }
    
     

Share This Page