Génération de sudoku aléatoire

Question

J'écris une fonction qui devrait générer des puzzles de sudoku aléatoires pour un projet de simulation; cette fonction prend comme argument le nombre de cellules à générer puis génère les indices de cellules et de nombres à mettre dans ces cellules. J'ai un problème dans la génération d'index de cellules, je ne suis pas un expert en programmation et je ne peux pas trouver une bonne routine pour générer des index et vérifier qu'il ne s'agit pas du même index deux fois ou plus. Le funcion est:

void gen_puzzle(int quanti) 
{ 
    if(quanti>81) exit(1); 
    indexes* ij=new indexes[quanti]; 
    int f,g,k, controllo=1; 

    do 
    { 
    for(f=0; f<9; f++) 
    for(g=0; g<9; g++) 
    { 
    puzzle[f][g].num=0;//puts 0 in the sudoku puzzle 
    puzzle[f][g].p=0; 
    } 

//////////////section to improve 
out: 
    srand(int(time(0)+clock())); 

    for(k=0; k<quanti; k++) 
    ij[k].i=casuale()-1, ij[k].j=casuale()-1;//generates random indexes of sudoku cells where put random nubers 

    for(f=0; f<quanti; f++) 
    for(g=f+1; g<quanti; g++) 
    { 
    if(ij[f].i==ij[g].i && (ij[f].j==ij[g].j)) goto out; 

    } 
//////////////////// 

    for(k=0; k<quanti; k++) 
    puzzle[ij[k].i][ij[k].j] . num=casuale();//puts random numbers in cells 
    } 
    while(dataNotGood()); //till sudoku isn't good 
} 

Je demande l'aide de la section où le funcion met les index aléatoires dans ij[] tableau, je l'ai utilisé un goto mais ce n'est pas une bonne solution et il ne se quanti est bien fonctionne pas plus alors 17 au sujet .
casuale() juste retourne un nombre aléatoire entre 1 et 9.

Answer 1

D'abord, je voudrais dépouiller toutes les directives #pragma omp parallel jusqu'à ce que vous avez du code qui fonctionne. En ce moment, cela réduit la lisibilité. Deuxièmement, si vous voulez générer des sudoku «non résolus» (c'est-à-dire ceux où la plupart des nombres ne sont pas remplis), vous remplissez habituellement quelques nombres au hasard et vous testez le sudoku en laissant l'ordinateur le résoudre . Si le groupe réussit, cela signifie que vous avez commencé avec un bon sudoku. Here vous trouverez une bonne explication d'un algorithme qui résout le sudokus. Troisièmement, sachez que les nombres que vous voulez mettre dans un puzzle de sudoku sont très limités. Si un bloc 3x3 (ou une ligne ou colonne 9x1) contient un 1, vous ne pouvez pas ajouter d'autres 1 au bloc (ligne, colonne), si un bloc 9x9 contient neuf 1, vous ne pouvez pas ajouter d'autres 1, etc. Donc, il est probablement préférable de remplir un tableau de tableaux avec tous les nombres que vous pouvez ajouter (neuf tableaux de 1 à 9 pour tous les blocs 3x3) et de retirer aléatoirement des éléments de ces tableaux et de les mettre dans le puzzle du bloc 3x3 correspondant. . De cette façon, vous évitez au moins la situation où vous ajoutez des numéros en double dans le même bloc 3x3.

Answer 2

Vous n'avez pas besoin d'un algorithme de génération de nombres aléatoires. Vous connaissez déjà les numéros: ils sont uniques et sont dans la plage 1..n, où n doit être <= 9 pour les cartes de sudoku de taille 9x9 ou inférieure. Ce dont vous avez besoin, c'est d'un moyen de mélanger les numéros 1..n, puis de les affecter aux «index». Pour le brassage, Fisher-Yates shuffle est assez simple et efficace. L'utilisation de cette fonction élimine le besoin d'une génération de nombres aléatoires et, espérons-le, de goto.

Answer 3

Ma suggestion: créer un puzzle complet (résolu) en utilisant un algorithme trouvé ailleurs, puis vous effacez au hasard un certain pourcentage des cellules.