GENERATEUR DE SUDOKU

package org.hag.sudoku;

import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.Random;

/**
 * 
 * This is a free Sudoko generator
 * using a brute force algorythm.
 * 
 * Random numbers are tested in a the
 * row, the colums and the square until
 * all the grid is completed.
 * 
 * @author Hubert.Gregoire@gmail.com
 * 
 *
 */
public class SudokuGen {

	
	private static final int INITIAL_VALUE = -1;
	
	private static short COLS = 9;
	private static short ROWS = COLS;
	
	private static final int PERCENT_HIDDEN = 85;
	
	static List randomList = new ArrayList();
	/**
	 * 
	 * Create a SUDOKU Grid
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] grid = new int[ROWS][COLS]; 
		int nbTry =0;
		
		initGrid(grid);
		long start = System.currentTimeMillis();
		
		while( !populateGridwithSuccess(grid)) {    //retry until the lines, 
			initGrid(grid);							//cols and square are correct
			nbTry++;
		}
		
		long end = System.currentTimeMillis();
		
		displayGrid( grid ,true);  // display the solution
		
		displayGrid( grid ,false); // display the game
		
		System.out.println("Computed in " + nbTry + " trys and " + (end - start) +"ms !" );
		
	}



	/**
	 * 
	 * Init the Grid with INITIAL_VALUE
	 * 
	 * @param tab, the empty grid
	 */
	private static void initGrid(int[][] tab) {
		for( short k = 0 ; k < tab.length ; k++) {
			for( short j = 0 ; j < tab[k].length ; j++) {
				tab[k][j] = INITIAL_VALUE;
			}		
		}
	}


	/**
	 * 
	 * Insert the numbers 
	 * 
	 * @param tab, the initialized grid
	 */
	protected static boolean populateGridwithSuccess(int[][] tab) {
		int failure = 0;
		int rand ;
		Random randomGenerator = new Random((new Date().getTime()));
		
		for( short k = 0 ; k < tab.length ; k++) {
				for( short j = 0 ; j < tab[k].length ; j++) {
					randomList.clear();
					do {
							rand = randomGenerator.nextInt(COLS)+1;   // generate a random number
							if( randomList.contains(rand ) ) {   // already tested
								continue;
							} else {
								randomList.add(rand);			// add to alreadyDonelist
								if(randomList.size() == COLS) {	// cancel if all tested
									rand = -1;
									failure ++;
									break;
								}
							}
					} while ( ! isAlone(rand,tab,k,j) ) ;
					tab[k][j] = rand;
					
				}		
			}		
			
			return (failure == 0 ) ; // success if no failure
	}
	
	/**
	 * 
	 * Returns true if the randomNumber is unique in the row, the line , the square
	 * 
	 * @param randomNumber
	 * @param tab
	 * @param row
	 * @param col
	 * @return
	 */
	protected static boolean isAlone ( int randomNumber, int[][] tab, int row, int col) {
		return  ( checkCol(randomNumber, tab, row, col,0,tab[row].length) && checkRow(randomNumber, tab, row, col,0,tab.length) && checkSquare(randomNumber, tab, row, col)) ;
	}
	
	/**
	 * Returns true if the column is good !
	 * 
	 * @param randomNumber
	 * @param tab
	 * @param row
	 * @param col
	 * @return
	 */
	private static boolean checkCol( int randomNumber, int[][] tab, int row, int col, int start, int end) {
		// rows before
		for( int i=start; i < row ; i++) {
			if( randomNumber == tab[i][col] )  
				return false;
		}
		// rows after
		for( int i=row; i < end -1 ; i++) {
			if( randomNumber == tab[i][col] )  
				return false;
		}
		return true;
	}

	/**
	 * Returns true if the square is good !
	 * 
	 * @param randomNumber
	 * @param tab
	 * @param row
	 * @param col
	 * @return
	 */
	private static boolean checkSquare( int randomNumber, int[][] tab, int row, int col) {
	
		int squareRowStart = (row/(ROWS/3)) * ROWS/3;  // square top left start
		int squareRowEnd = squareRowStart + ROWS/3;  // square top right end
		
		int squareColStart = (col/(COLS/3)) * COLS/3; // square bottom left start
		int squareColEnd= squareColStart + COLS/3; // square bottom right end

		for( int k = squareRowStart ; k <squareRowEnd ; k++) {
			for( int j = squareColStart ; j <squareColEnd ; j++) {
				if( randomNumber == tab[k][j] )  
					return false;
			}		
		}
		return true;

	}

	/**
	 * Returns true if the row is good !
	 * 
	 * @param randomNumber
	 * @param tab
	 * @param row
	 * @param col
	 * @return
	 */
	private static boolean checkRow( int randomNumber, int[][] tab, int row, int col, int start, int end) {
		//  cols before
		for( int i=start; i < col ; i++) {
			if( randomNumber == tab[row][i] )  
				return false;
		}
		// cols after
		for( int i=col; i < end  ; i++) {
			if( randomNumber == tab[row][i] )  
				return false;
		}
		return true;
	}

	protected static void displayGrid(int[][] tab, boolean solution) {
		Random randomGenerator = new Random((new Date().getTime()));
		
		System.out.println("------------------------------");
		System.out.println("--- S U D O K U Generator ----");
		if(solution)
			System.out.println("---       Solution        ----");
		else
			System.out.println("---        Game           ----");
		System.out.println("---- by    H.Gregoire     ----");
		System.out.println("------------------------------");
		System.out.println("");
		for( short k = 0 ; k < tab.length ; k++) {
			for( short j = 0 ; j < tab[k].length ; j++) {
				if (solution) {				// display the solution
					System.out.print(tab[k][j] + " .");
				} else {					// display the game
					if( randomGenerator.nextInt(100) < PERCENT_HIDDEN) {  // percent hidden number
						System.out.print("* .");
					} else {
						System.out.print(tab[k][j] + " .");
					}
				}
				
			}		
			System.out.println(" ");
		}
		System.out.println("------------------------------");
	}
}