GENERATEUR DE SUDOKU

---

Commentaire sur cette source (2)
Ajouter un commentaire et/ou une note

Ce petit programme génère une grille de sudoku (puzzle de nombre japonais)
ainsi que sa solution, avec un algorythme assez rudimentaire puisque qu'il
est basé sur une serie d'essais avec des nombres aléatoires, en général il
propose une solution en moins de 5 minutes.

Bon jeu.
PS: on peut changer la difficulté en faisant varier le pourcentage de cases
cachées, ainsi que la taille de la grille.

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("------------------------------");
	}
}

• CRÉATION DE SUDOKU AU HASARD ("BACKTRACKING" ET "DANCING LINK")
• QUIZ DU CULTURE GENERALE
• SIMPLE TETRIS FLUIDE
• JEU DU CENT (APPLET)
• JEU LE PENDU

• JEU D'ECHEC
• MEMORYGAME
• JEU SUSAN
• ABALONE JAVA
• SUDOKU AMÉLIORÉ