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.
Source / Exemple :
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("------------------------------");
}
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.