Discussion :

[mathematicien]

Je suis prof de maths et débute dans la programmation et je souhaite créer un programme en Pascal qui génère des grilles de Sudoku en permutant deux lignes d'un même bloc entre elles, deux colonnes d'un même bloc entre elles et deux blocs entre eux horizontalement et verticalement.

Un bloc est une sous-grille de 3 lignes (ou colonnes) "l1,l2,l3" ou "l4,l5,l6" ou "l7,l8,l9" ou "c1c2c3" ou "c4c5c6" ou "c7c8c9" (l=ligne c=colonne).
Et tout cela de façon aléatoire!!!

ATTENTION : deux lignes (ou colonnes) de 2 blocs distincts ne peuvent pas etre permutées sinon on perdrait l'unicité et même peut-être l'existence de la solution de la grille de Sudoku ?

L’algorithme serait :
Pour chaque bloc il y a 6 façons de permuter les lignes (ou colonnes), chaque permutation on lui administre un chiffre 1 ou 2 ou..ou 6.
L'algo serait de définir de façon aléatoire un nombre entre 0 et 1 (exclus) avec 8 décimales celles-ci comprises entre 1 et 6 (sinon prendre le reste de sa divisions euclidienne par 6) dont :
la 1° décimale correspondrait a la permutation du 1er bloc verticale(les 3 premières colonnes)
la 2° du 2° bloc (les 3 colonnes suivantes)
la 3° du 3° bloc (les 3 dernières colonnes)
la 4 du 1° bloc horizontale
la 5° du 2° bloc horizontale
la 6° du 2° bloc horizontale
la 7° des blocs horizontaux entre eux
la 8° des bloc verticaux entre eux

Chaque fois qu'un nombre sera généré cela entraînera une combinaison de permutations et donc une nouvelle grille!!!
Voilà pour l'algo !!!

Pour la programmation comme je découvre je ne sais pas du tout comment m'y prendre, merci de m'aider !!!

Merci de votre aide.

[cchatelain]

Je n'arrive pas à cerner avec précision votre soucis :
- avez vous un problème dans la conception de l'algo qui permute les colonnes ?
- avez vous un soucis avec la structure de stockage des colonnes ?
- avez vous un algo que vous n'arrivez pas à concrétiser en pascal ?

[etranger]

Si jamais il y a ce post qui m'avais bien aider pour implementer un solveur de sudoku (malheureusement en java) : http://www.developpez.net/forums/sho...t=54373&page=1

[mathematicien]

L’algorithme serai*:
Pour chaque blocs il y a 6 façons de permuter les lignes (ou colonnes),chaque permutation on lui administre un chiffre 1 ou 2 ou..ou 6.
l'algo serai de définir de façon aléatoire un nombre entre 0 et 1 (exclus) avec 8 décimales celles-ci comprises entre 1 et 6 (sinon prendre le reste de sa divisions euclidienne par 6) dont :
la 1° décimale correspondrait a la permutation du 1er bloc verticale(les 3 premières colonnes)
la 2° du 2° bloc (les 3 colonnes suivantes)
la 3° du 3° bloc (les 3 dernières colonnes)
la 4 du 1° bloc horizontale
la 5° du 2° bloc horizontale
la 6° du 2° bloc horizontale
la 7° des blocs horizontaux entre eux
la 8° des bloc verticaux entre eux
Chaque fois qu'un nombre sera généré cela entraînera une combinaison de permutations et donc une nouvelle grille!!!
voila pour l'algo!!!
pour la programmation comme je découvre je ne sais pas du tout comment m'y prendre ,merci de m'aider!!!

[gorgonite]

déjà il faut modéliser...

comment représenter les grilles ?
comment représenter les cellules ?

ensuite, faire les fonctions élémentaires (permutations, etc.)

enfin, empiler les briques...

[Eric Sigoillot]

pour la programmation comme je découvre je ne sais pas du tout comment m'y prendre

Commencer par consulter nos resources en ligne serait un très bon début. On ne s'improvise pas programmeur.
http://pascal.developpez.com

[mathematicien]

comment constuit-on un permutation de lignes (par exenple) dans une grille?
et aprés le programme construit comment fait-on pour l'interface ,je voudrait que sur l'ecran apparaissent une grille et en appuyant sur entter une autre grille est generer
merci

[Tuxico]

wowowo doucement

il faut commencer par les bases...lis le cours de pascal de developpez.net, la faq, essaye de commencer ton programme sur papier, par des idées d'algo etc. et reviens quand tu auras un problème concret

[gorgonite]

comment constuit-on un permutation de lignes (par exenple) dans une grille?
et aprés le programme construit comment fait-on pour l'interface ,je voudrait que sur l'ecran apparaissent une grille et en appuyant sur entter une autre grille est generer
merci

bah une permutation... si tu as un tableau de neuf cases contenant les valeurs, tu fais 4 random entre 1 et 10, et tu déplaces la case k concernée avec la 10-k par exemple (en plus avec un nombre pair ça marche mieux)

[mat.M]

Pour la programmation comme je découvre je ne sais pas du tout comment m'y prendre, merci de m'aider !!!

Merci de votre aide.

Formaliser une grille n'est pas terriblement compliqué en soi il suffit de prendre un tableau d'integers integer : array[1..valeur];
Après c'est à toi en tant que mathématicien de trouver les bonnes procédures de tri, pernutation etc..

Gorgonite a donné un bon élément de réponse

[random]

je ne vois pas trop pourquoi tu veux règler ce problème par permutation

en fait on travaille généralement ainsi

on écrit un solveur

ensuite on tire un nombre au hasard de 1 à 9 que l'on adresse au solveur avec
l'adresse A1 exemple 7 aprés avoir inhibé la fonction essai erreur du solveur

le solveur renvoie les solutions possibles par exemple 12345689 pour b1
on retire au hasard par exemple 6 et on adresse la solution au solveur
qui renvoie pour c1 1234589

on tire ainsi les quatres carrés situés aux quatre coins jusqu'a l'obtention d'une solution unique par le solveur

on dispose alors d'une grille nouvelle aléatoire complète

on tire alors dans cette grille des emplacements au hasard jusqu'à résolution par le solveur

on dispose alors d'une solution de force normale

pour obtenir une grille plus facile il suffit d'ajouter 1 ou plusieurs nombres

pour obtenir une grille plus facile on réactive la fonction essai erreur du solveur et on retire 1 ou deux emplacements en vérifiant que le solveur trouve bien la solution

[random]

suite à des questions privées sur cette question je m'explique un peu

un solveur (de sudoku) est un programme permettant de résoudre un problème de sudoku
il est composé de deux parties
l'interface
qui permet de soumettre les chiffres du problème
généralement c'est un tableau à double entrée généralement accompagné
d'une notation de position type bataille navale
et de donner la solution ou son évolution
le solveur lui même qui résoud le problème
voir wikipedia sur les modes de résolution
comment programmer
on construit une matrice(1..9,"A".."I") dans laquelle on loge "123456789" dans chaque cellule
si dans l'interface on donne 1 en A1
dans la matrice on écrit (1,"A") "1"
(2..9,"A") "23456789" colonne
(1,"B".."I" ) "23456789" ligne
(1,"B".."C") "23456789" carré
etc

ensuite on rercherche pour chaque ligne et chaque colonne si il reste un emplacement unique pour un chiffre si oui on le place comme s'il entait dans l'interface

la simple application de ces algos et de leurs dérivés résoud les problèmes facile et difficile

restent les problémes qui résistent à ce niveau de solveur

pour ceux là on écrit un module complémentaire essai/erreur
dans la grille du solveur on sélectionne les cases comprenant deux candidats

supposons colonne c deux emplacements "17" soit deux possibiltés de placement je fais 2 copies de la matrice dans la première je place 1
et dans la seconde 7

je calcule mes grilles copies si l'une des deux conduit à une impossibilité
je retiens l'autre

cette partie bien écrite (niveau programmation moyen) niveau algo moyen
permet de résoudre tous les problèmes

le générateur de problèmes est plus facile il est composé
de deux parties
le générateur de grille
je tire des nombres au hasard dans les quatre carrés aux angles
je les entre dans l'interface
je récupère la grille du solveur et je tire auhasard
exemple début en a1 j'ai dans la grille du solveur "123456789"
si je tire 5
je récupère dans mon solveur "12346789" parmi lesquels je vais effectuer
mon tirage
rapidement le problème est résolu
je dispose à ce moment d'une grille aléatoire
le générateur de problème
je fais une copie de ma grille aléatoire
j'inhibe la fonction essai erreur du solveur
je tire des emplacements au hasard dans cette grille
par exemple (3,"C3) qui contient 9
que j'entre dans le solveur via l'interface d'entrée
jusqu'à résolution du problème

les chiffres qui ont permis de résoudre le problème et leur emplacement
font un problème nouveau

[Loceka]

Sinon, une solution simple qui garderait l'idée des permutations serait de créer 10 matrices 3,3 :

• 9 matrices d'entiers, correspondants aux 9 blocs internes de la grille
  de type : bloc = array [1..3,1..3] of integer;
• 1 matrice de pointeurs, regroupant ces 9 matrices.
  de type : grille = array [1..3,1..3] of ^bloc;

Après, il suffit de tirer aléatoirement (2 fois 10) chiffres compris entre 1 et 3 et de permuter les lignes/colonnes des matrices correspondantes.

Quant à comment permutter deux variables, je te laisse le soin de consulter les liens donnés plus haut, ça fait partie des bases.

[random]

non loceka

si je tire en matrice 1
matrice 1 (1 2 3
4 5 6
7 8 9) il est evident que les matrices 2 3 4 7 seront différentes