Bonjour!! Alors je suis sur le tuto langage C ( merci au passage pour le temps consacré) et j'aime bien me faire mes propres exercices afin de bien exercer plusieurs notion de chaque chapitre.
Déjà dans la parti No1 après avoir apprit à faire des numéro aléatoires, je me suis dis que je serais capable de faire un générateur de Sudoku ( certe avec beaucoup de ligne et surtout les 81 chiffres à codé^^, mais j'en étais satisfait de pouvoir savoir que je pouvais le faire).
J'ai avancé dans la théorie et là je viens de finir le chapitre sur les tableaux, et je me suis dis: bon ben avec les tableaux ce sera encore plus mieux pour un sudoku alors mettons nous enfin à la patte et faisons ce générateur...
Hum la hâte s'empara de moi, et je me mis a coder quand soudainement ce matin...je comprends c'est pas possible...
Voilà le code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Sudoku.h"
long totalCarr=0;
long totalLign=0;
void addCarr(long tableau[]);
void gene(long tableau[],long tailleTableau);
int main()
{
long tableau[80]={0};
gene(tableau,81);//Generation des chiffres aleatoires 0-80=81 nombre. On met [81] et non pas [80] car il faut 1 inférieur pour la borne.
printf("\n\nA1:%ld ,A2:%ld, A3:%ld, I9:%ld \n",tableau[0],tableau[1],tableau[2],tableau[80]);
return 0;
}
void gene(long tableau[],long tailleTableau)//GENERATEUR DE NUMERO ALEATOIRE SUR LES 81 CASES
{
const long MAX=9, MIN=1;
long i=0,nbreSudoku=0;
long totalA=0,totalB=0,totalC=0,totalD=0,totalE=0,totalF=0,totalG=0,totalH=0,totalI=0;
srand(time(NULL));
//do
//{
for(i=0;i<tailleTableau;i++)// CREATION ALEATOIR DE 81 numero OK!!
{
nbreSudoku = (rand() % (MAX - MIN + 1)) + MIN;
tableau[i]=nbreSudoku;
}
do
{
for(i=0;i<10;i++)
{
totalA+=tableau[i];
//printf("Tableau no %ld, valeur %ld\n\n",i,tableau[i]);
}
}while(totalA!=45);
/*
for(i=9;i<19;i++)
{
totalB+=tableau[i];
}
for(i=18;i<28;i++)
{
totalC+=tableau[i];
}
for(i=27;i<37;i++)
{
totalD+=tableau[i];
}
for(i=36;i<46;i++)
{
totalE+=tableau[i];
}
for(i=45;i<55;i++)
{
totalF+=tableau[i];
}
for(i=54;i<64;i++)
{
totalG+=tableau[i];
}
for(i=63;i<73;i++)
{
totalH+=tableau[i];
}
for(i=72;i<82;i++)
{
totalI+=tableau[i];
}
}while(totalA+totalB+totalC+totalD+totalE+totalF+totalG+totalH+totalI!=405);
*/
}
Mon idée était la suivante:
D'abord faire un code qui permet de générer aléatoirement les 81 cases de mon tableau ( 81 cases dans le sudoku noté de 1-9.
Puis afin qu'il n'y ai pas plusieurs chiffres identique par case, alors j'ai fait la somme de série de 9 numéro, ainsi que l'addition des 9 séries. Le sudoku contient 81 petite cases, 9 grandes cases qui contiennent les 81 petites, et 1 IMMENSE case qui contient tout. ( débuts ligne 51) J'ai donc additionné les 9 petites cases pour chaque grand case, ce qui dois donner un résultat de 45(1+2+3+4..+9=45), puis additionner les grandes cases. Pour que le toute soit validé la condition est que: Le total des grandes cases additionnées vaut 45 fois 9= 405.
Ensuite la deuxième condition, et là c'est plus dur et je l'ai pas fait, était de calculer la somme des petites cases en LIGNE de façon à faire 45, puis que l'addition des 9 ligne = 405 pour que ce soit valider. Si vous connaissez le sudoku, vous savez que pour qu'un sudoku soit juste, il ne doit pas avoir le meme numéro par ligne horizontale et verticale, ainsi que dans les grandes cases, voilà d'ou provienne ces deux conditions que j'ai voulu faire.
LE PROBLEME:
Le problème et bien c'est que déjà l'ordi n'arrive pas à faire la première condition. Et même si je limite cette condition à(ligne 45): "Génère 9 numéro que si on fait leur somme on obtient 45" il n'arrive déjà pas!!!! Et je le comprends car il doit trouver les bons résultats parmi 9^9 solutions.
Alors comment faire? Est ce possible? En tout cas je comprends que avec mon niveau je suis incapable de le faire. Il faudrait carrément que l'ordinateur enregistre toute les combinaisons qui ne marche pas afin de faire un filtre, mais ça prendrais une plombe à faire, sans compter qu'il y a d'autres condition après :S!
J'ai une idee qui pourait peut etre t'aiguiller , mais c'est loin d'etre simple.
Tu peux essayer de faire un brut force recusif(tester toutes les valeurs possibles) sur ta grille.
Je m'explique.
Pour ta premiere ligne tu la remplis uniquement correctemet en generant un nombre aleatoirepour chaque cas , tout en faisant attention a ne pas repeter ce nombre.
exemple : 5 2 1 3 4 8 9 7 6
Tu remplis toutes tes lignes de cette facons mais en veifiant a chaque fois la possibilite de mettre le nombre dans la case , si aucun nombres ne peut y aller , tu reviens en arriere (grace a la recursivite) et tu test avec un autre chiffre.
Cela n'est qu'une idee.
Pas simple a mettre en place , mais je pense que ca peut marcher.
Hum hum!!! Donc genre No1 = 3, donc No2 peut être = 1 ||2||4||5||6||7||8||9 sinon on avance pas. Si Condition ok on avance et ainsi de suite? hum hum... ok pour cette condition, c'est très bien pensé^^, bien plus sélectif!! mais après le souci c'est qu'il faut faire valoir cette condition dans l'autre condition: une grande case contient 9 numéro de 1-9 non identique. donc si ça joue pas il devra tout recalculer la condition 1 et ainsi de suite.....ça prendra un temps infini et ce sera x chance sur9^9^9 que ça joue^^ lol...
Pourtant je sais que les générateurs de sudoku ça existe , comment font ils
-premièrement :tu ferais mieux de te servir des tableau à deux dimensions exemple:
long tableau[9][9];
ça te permettra de mieux repérer tes cases
-deuxièmement :la condition de la somme n'est pas suffisante car (par exemple)
1+2+3+4+5+6+7+8+9=90=1+2+2+5+5+6+7+8+9 il faut utiliser deux boucles imbriquées pour pouvoir vérifier la condition de non répétition
-troisièmement :la génération aléatoire ne permet pas de passer sur tout les cas si on ne lui indique pas qu'il ne faut pas refaire le même cas déjà proposé
je me suis dis que je serais capable de faire un générateur de Sudoku" ( certe avec beaucoup de ligne et surtout les 81 chiffres à codé^^,
Je ne suis pas sûr que tu aies bien compris ce que le terme "générateur de sudoku recouvre. Il s'agit de créer une grille non pleine (je crois que tu engendres des grilles pleines) et admettant une unique solution. Si tu veux un algorithme, en voici un trouvé sur le site de Jean-Paul Davalan :
Algorithme
L'algorithme du générateur est le suivant :
1) a) Construction d'une grille complète de 81 cases. b) Choix d'un ordre de parcours des 81 cases.
2) Tout au long du parcours, on vide la case k et on résoud la grille incomplète, s'il y a plus d'une solution on replace l'élément dans la case k.
Vous remarquez à chaque étape deux nombres s'afficher, par exemple '32 28'. Dans cet exemple il reste 28 cases à parcourir et 32 ne sont pas vides, c'est donc que 32-28=4 nombres ont été replacés dans leur case.
Lorsque l'algorithme se termine l'affichage est par exemple '26 0', vous êtes certains que la grille a une soution unique, ce qui ne serait pas le cas si on enlevait l'un des 26 nombres restants. Évidemment une même grille complète peut éventuellement être obtenue à partir de grilles incomplètes différentes (lorsque l'ordre de parcours de l'algorithme change).
Citation : -ed-
Citation : MegaNoob
Pourtant je sais que les générateurs de sudoku ça existe , comment font ils ?
Ce sujet est rebattu sur les forums d'algorithmes...
Rebattu ? c'est ce qu'on croit mais la question de la génération efficace d'un sudoku est beaucoup plus difficile que la création d'un solveur. Sur le forum algorithmes-developpez, cette question a été très peu évoquée : 3 messages parmi la recherche ici (et les réponses données sont très médiocres).
A mon avis, il faux générer aléatoirement le 1er chiffre puis générer les autres en choisissant le chiffre dans une liste comprenant les chiffres de 1 a 9 auxquels on a supprimé les chiffres qui ont une occurrence dans la ligne, la colonne et le groupe de 9 cases de la case à remplir.
Ainsi, l ordi ne perd pas de temps à générer jusqu'à ce que les conditions soient respectées.
Enfin, j ai pas beaucoup dexpérience et c'est comme ça que je m'y prendrait.
Ça m'a donné envie d'essayer mais j'élaborerais l'algo en python (plus clair)
J'ai le même projet que MegaNoob depuis le début de la journée, à quelques différences près :
- Je ne souhaite obtenir uniquement des grilles uniques, c-a-d non générées par retournement de grille ou permutation de colonne/ligne
- Je souhaite obtenir des proposition de grilles ne possédant que 17 indices au départ, n'acceptant qu'une seule et unique solution (c'est le minimum, d'après une équipe de matheux irlandais)
- Et j'aimerais aussi connaitre le nombre de grilles que je peux créer au maximum en utilisant ces contraintes (Via mathématiques, pas en les listant puis comptant toutes). Mais ça c'est du bonus :o.
Pour l'instant, j'ai l'impression que mon troisième souhait n'est pas réalisable, et je n'ai pas encore trop planché sur les deux première, mais il est clair que je dois commencer par lister toutes les solutions uniques possibles, puis retirer les (81 - 17) bon chiffres pour retrouver uniquement la solution initiale sur chaque grille crée.
Y'a déjà un mec qui a commencé à faire cette liste, non exhaustive : http://staffhome.ecm.uwa.edu.au/~00013890/sudokumin.php
Bonjour, bien que ce topic soit vieux, je me permets de proposer mon code. Il permet une génération de sudoku assez rapide. Il peut aussi résoudre un sudoku si vous lui passer le chemin d'un fichier en parametre. Mais ça reste dans l'idée du brut force.
Actuellement, j'ai trouvé quelques pistes mathématiques à explorer, mais je trouve que ça manque d'aléatoire. En espérant que mon code vous aidera.
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <fstream>
typedef struct s_case
{
int nb;
std::vector<int> restrict;
bool isLock;
} t_case;
bool isNotEnd(t_case game[81])
{
for (unsigned int i = 0; i < 81; ++i)
if (game[i].nb == 0)
return (true);
return (false);
}
bool isInRow(int nb, t_case game[81], int index)
{
index /= 9;
index *= 9;
for (unsigned int i = index; i < index + 9 && i < 81; ++i)
if (game[i].nb == nb)
return (true);
return (false);
}
bool isInColumn(int nb, t_case game[81], int index)
{
index %= 9;
for (unsigned int i = index; i < 81; i += 9)
if (game[i].nb == nb)
return (true);
return (false);
}
bool isInSquare(int nb, t_case game[81], int index)
{
int y = index / 9;
int x = index % 9;
x = x / 3 * 3;
y = y / 3 * 3;
for (unsigned int i = y; i < y + 3; ++i)
for (unsigned int j = x; j < x + 3; ++j)
if (game[i * 9 + j].nb == nb)
return (true);
return (false);
}
void givePossibleNumber(std::vector<int> &vec, t_case game[81], int index)
{
vec.clear();
for (unsigned int i = 1; i < 10; ++i)
if (!isInRow(i, game, index) && !isInColumn(i, game, index) && !isInSquare(i, game, index))
{
bool test = true;
for (unsigned int j = 0; j < game[index].restrict.size(); ++j)
if (i == game[index].restrict[j])
test = false;
if (test)
vec.push_back(i);
}
}
void generateSudoku(t_case game[81])
{
int nb;
int index = 0;
std::vector<int> vec;
srand(time(NULL));
while (isNotEnd(game))
{
givePossibleNumber(vec, game, index);
if (vec.size() != 0)
{
nb = vec[rand() % vec.size()];
if (!isInRow(nb, game, index) && !isInColumn(nb, game, index) && !isInSquare(nb, game, index))
{
game[index].nb = nb;
++index;
}
}
else
{
game[index].restrict.clear();
--index;
game[index].restrict.push_back(game[index].nb);
game[index].nb = 0;
}
}
}
void solveSudoku(t_case game[81], char *file)
{
std::ifstream infile(file);
std::string line("");
int index = 0;
int nb;
std::vector<int> vec;
while (std::getline(infile, line))
{
for (unsigned int i = 0; i < line.size(); ++i)
{
game[index].nb = line[i] - 48;
if (game[index].nb != 0)
game[index].isLock = true;
++index;
}
}
index = 0;
while (game[index].isLock)
++index;
while (isNotEnd(game))
{
givePossibleNumber(vec, game, index);
if (vec.size() != 0)
{
nb = vec[rand() % vec.size()];
if (!isInRow(nb, game, index) && !isInColumn(nb, game, index) && !isInSquare(nb, game, index))
{
game[index].nb = nb;
++index;
while (index < 81 && game[index].isLock)
++index;
}
}
else
{
game[index].restrict.clear();
--index;
while (index != 0 && game[index].isLock)
--index;
if (index == 0 && game[index].isLock)
{
std::cout << "Sudoku Impossible" << std::endl;
break;
}
game[index].restrict.push_back(game[index].nb);
game[index].nb = 0;
}
}
}
int main(int ac, char **av)
{
t_case game[81];
memset(game, 0, sizeof(t_case) * 81);
if (ac < 2)
generateSudoku(game);
else
solveSudoku(game, av[1]);
for (unsigned int i = 0; i < 81; ++i)
{
if (i != 0 && i % 9 == 0)
std::cout << std::endl;
std::cout << game[i].nb;
}
std::cout << std::endl;
return (0);
}
Désolé pour l'indentation, j'ai fait ça avec blocnote.
- Edité par JérémieMortier 24 juillet 2017 à 11:47:03
Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.
Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre. En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.
Au lieu de déterrer un sujet il est préférable :
soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
soit de créer un nouveau sujet décrivant votre propre contexte
ne pas répondre à un déterrage et le signaler à la modération
Je ferme ce sujet. En cas de désaccord, me contacter par MP.
Moderateur forum || FAQ 3D || discord 3D francophone || OC Tweak script