Generateur de sudoku

Soyez le premier à donner votre avis sur cette source.

Snippet vu 23 357 fois - Téléchargée 33 fois

Contenu du snippet

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

A voir également

Ajouter un commentaire Commentaires
Messages postés
15
Date d'inscription
vendredi 4 mars 2005
Statut
Membre
Dernière intervention
13 avril 2006

j'ai essayé de tester ce sudoku j'ai un probleme avec eclipse au niveau du contains et du add ligne
93 et 96 :s
Messages postés
2
Date d'inscription
jeudi 18 novembre 2004
Statut
Membre
Dernière intervention
15 février 2006

Bien qu'assez lent, comparé à celui de sudoku.sourceforge.net, il fait ce qu'on lui demande (mais ce n'est pas symétrique :s)

Bravo en tout cas !

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.