Go4Expert

Go4Expert (http://www.go4expert.com/)
-   Java (http://www.go4expert.com/forums/java/)
-   -   Sudoku generation algorithm in JAVA : Any suggestions for improvement? (http://www.go4expert.com/forums/sudoku-generation-algorithm-java-t27665/)

ManzZup 25Jan2012 23:16

Sudoku generation algorithm in JAVA : Any suggestions for improvement?
 
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));
    }
        }
}



All times are GMT +5.5. The time now is 03:46.