Discussion :

[FullSpeed]

En dessous de 17 révélés tous les problèmes ont plusieurs solutions
Boris

Je voudrais commencer la journée en saluant chaleureusement
celui qui dans l'ombre corrige mes messages pour les mettre en français
Merci à toi
Boris

[Félix Guillemot]

Yeah !

Edit : Est ce quue quelqu'un verrait comment, par la logique, continuer de résoudre cette grille ?? Les solveurs d'internet n'y arrivent pas ! Et la solution est unique !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
084210590
056409800
009058040
047501938
508090004
931804075
090045780
800900450
475182369

Je cherche a savoir quelle technique il faudrait que je code !

Mick, cette grille se résoud par la logique, et sans hypothèses.
Mon solver la résoud par la logique seule (0,8ms machine de 2005).
Par contre, si je te donne les méthodes logiques, ce n'est plus drôle

A+

[Félix Guillemot]

Mick, cette grille se résoud par la logique, et sans hypothèses.

Oups ! Erreur de ma part, j'avais mal vu : non, il a fallu poser une hypothèse, mais la résolution reste effective en "un rien de temps"

[FullSpeed]

Nous avons la un problème de définition:
Pour aller plus loin dans ta grille on va utiliser la méthode de 'couleurs"
c'est a dire une méthode d'hypothèses parfaitement maitrisée. Et donc doit-on considère que la méthode des couleurs est une méthode logiue
ou une méthode Brute force

En réalité les soldeurs par restriction ou contrainte (essai de tous les candidats possibles) utilisent la méthode des couleurs

En fait toutes les problemes sont solubles en n'utilisant que les couleurs
car couleur = hypothèse

Boris

[mick605]

Mon solver la résoud par la logique seule (0,8ms machine de 2005).

C'est rapide, mais je vous donne directement la simplification ! L'énoncé a beaucoup moins de valeurs.

Oups ! Erreur de ma part, j'avais mal vu : non, il a fallu poser une hypothèse, mais la résolution reste effective en "un rien de temps"

Haha, je m'en doutais ! Pourtant je pense que c'est possible sans (toujours la meme chose) !

Pour aller plus loin dans ta grille on va utiliser la méthode de 'couleurs"
c'est a dire une méthode d'hypothèses parfaitement maitrisée. Et donc doit-on considère que la méthode des couleurs est une méthode logiue
ou une méthode Brute force

Je dirais, une méthode logique avec hypothese ! Je connaissais déja cette technique, ce n'est rien d'autre que des techniques que nous appliquons déja en vrai. C'est juste pour aller plus vite a l'écrit. Mais, pour l'instant, je code autre chose

Bon sinon, je viens de me faire une petite fonction récursive qui me trouve les candidats doubles, triples, ..., octuples !!

[ShaiLeTroll]

Tous les Sudokus y compris AI Escargot sont résolus par la logique. Il faut chercher ces méthodes logiques. Imbriquées les unes dans les autres et purement traduites en algo, elles sont efficientes.
Il faut s'intéresser un peu au sudoku et les chercher.
Dans cet exercice, c'est cette recherche de méthodes qui est intéssante, s'arrêter à la boucle la plus rapide, c'est dommage.
Quand je dis par la logique, je n'exclue pas l'éventualité de poser une hypothèse quand cela est nécessaire pour explorer deux scénrarii ou plus.
Il n'y a pas une seule vérité ou une seule méthode, c'est la combinaison de ces méthodes qui fait la force de la méthode.

Tout à fait, d'accord, pour le moment, je n'ai bossé que 4 heures sur mon Sudoku Solver, la 1er Algo de résolution des grilles faciles et moyennes fut rapidement au point, maintenant, je n'avance plus ... j'ai un algo en tête, mais il ne veut pas sortir, faut que je le couche sur le papier ... avant de penser à la performance, je m'interesse juste à sa réussite et cela risque d'être long car j'ai enfin un peu de temps pour tester D2009 (Trial), et migrer les 1ers éléments de la lib interne de mon employeur, enfin un taf interessant !
J'essayerais quand même d'avancer mon sudoku ... qui lui restera en D6

[Félix Guillemot]

Tout à fait, d'accord, pour le moment, je n'ai bossé que 4 heures sur mon Sudoku Solver, la 1er Algo de résolution des grilles faciles et moyennes fut rapidement au point, maintenant, je n'avance plus ... j'ai un algo en tête, mais il ne veut pas sortir, faut que je le couche sur le papier ... avant de penser à la performance, je m'interesse juste à sa réussite et cela risque d'être long car j'ai enfin un peu de temps pour tester D2009 (Trial), et migrer les 1ers éléments de la lib interne de mon employeur, enfin un taf interessant !
J'essayerais quand même d'avancer mon sudoku ... qui lui restera en D6

Je suis d'accord avec ta démarche : d'abord la méthode bien formalisée et ensuite le code, et ensuite l'optimisation.
Il faut savoir que je n'ai fait aucun effort d'optimisation de mon code. A l'époque, quand j'ai vu que l'application mettait 1 milliseconde pour la plupart des grilles avec un 20ms pour AI Escargot, je n'ai même pas cherché à aller plus loin, parce que c'est suffisant, en tant qu'utilisateur, je ne verrai pas la différence entre ça et 1 pico seconde.
Ensuite, une fois que l'algo est rôdé et que l'appli marche bien, je peux toujours m'amuser à gratter des micro-secondes, ce qui constitue une discipline en soi tout à fait consistante.
Celui qui gagnera le concours de vitesse au final est celui qui aura la meilleur méthode, car une fois optimisée en term de code, elle sera imbattable à mon avis.
On pourrait faire un concours d'optimisation en partant tous du même code, mais ceci ferait l'objet d'un autre défi.


Ps : ton code en D6 est compilable directement en 2009 à mon avis.

[mick605]

ShaiLeTroll > Je viens de trouver un truc super : C'est que tu peux resoudre plein de grilles diaboliques avec UNE SEULE fonction.

Est ce que tu as déja entendu parler des candidats Doubles, triples, quadruples, et des paires cachées, triplets cachés, ... (j'imagine que oui) Ben, sur une zone donnée, si il y a 5 cases vides, rechercher une paire cachée, c'est comme rechercher des candidats triples.

En fait, pour une ligne a X cases vides, rechercher un ensemble Nieme caché, c'est comme rechercher des candidats (X-N)ieme

Donc, si tu arrives a coder une fonction (récursive ) qui recherche des candidats Nieme, tu resoud en meme temps les ensembles cachés, et tu pourras résoudre plein de grilles diaboliques. (ensuite, faut l'optimiser, parce que niveau vitesse, ...)

[Félix Guillemot]

ShaiLeTroll > Je viens de trouver un truc super : C'est que tu peux resoudre plein de grilles diaboliques avec UNE SEULE fonction.

Est ce que tu as déja entendu parler des candidats Doubles, triples, quadruples, et des paires cachées, triplets cachés, ... (j'imagine que oui) Ben, sur une zone donnée, si il y a 5 cases vides, rechercher une paire cachée, c'est comme rechercher des candidats triples.

En fait, pour une ligne a X cases vides, rechercher un ensemble Nieme caché, c'est comme rechercher des candidats (X-N)ieme

Donc, si tu arrives a coder une fonction (récursive ) qui recherche des candidats Nieme, tu resoud en meme temps les ensembles cachés, et tu pourras résoudre plein de grilles diaboliques. (ensuite, faut l'optimiser, parce que niveau vitesse, ...)

ça me paraît intéressant...

[mick605]

ça me paraît intéressant...

Et je peux te dire que ca marche du tonerre ^^

[FullSpeed]

Le code est compatible a une donnée pret:
avec D2009 les strings sont en Unicode: chaque caractère est codeé sur 16 bits
Toutes les array of char (comme les string) doivent etrte remplacés par de array of byte si tu as besoin de conserver une taille de 8
Les delete et autre fillchar réservent quelques surprises.
A part cela le code marche bien
Si tu fais par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
Inc(byte(Monhstring[8])):

cela ne compile pas.
Il fait définir mon string: array of byte et non string
C'est parfois un gros boulot

Boris

[EDIT]

Quelqu'un aurait-il des routines rusées pour inverser ou
pivoter de 90° une matrice: faire que les colonnes
deviennent rangées?
Merci
[\EDIT]

[ShaiLeTroll]

ShaiLeTroll > Je viens de trouver un truc super : C'est que tu peux resoudre plein de grilles diaboliques avec UNE SEULE fonction.

Est ce que tu as déja entendu parler des candidats Doubles, triples, quadruples, et des paires cachées, triplets cachés, ... (j'imagine que oui) Ben, sur une zone donnée, si il y a 5 cases vides, rechercher une paire cachée, c'est comme rechercher des candidats triples.

En fait, pour une ligne a X cases vides, rechercher un ensemble Nieme caché, c'est comme rechercher des candidats (X-N)ieme

C'est effectivement, mon idée, j'ai tous les candidats possibles pour chaque case, et pensais tester un par un tous les arrangements ... parmis les candidats via un arbre ... selon une approche totalement empirique

[Pascal Fonteneau]

Bonjour

Je pars en juillet et je serai chargé en Aout coté boulot.

Alors, j'ai adressé ma solution a Felix.

Je passerai ici entre 2;

Pour moi , les dès sont jetés.

Bonne chance à tous.

Pascal

[Félix Guillemot]

Bonjour

Je pars en juillet et je serai chargé en Aout coté boulot.

Alors, j'ai adressé ma solution a Felix.

Je passerai ici entre 2;

Pour moi , les dès sont jetés.

Bonne chance à tous.

Pascal

Arg ! Pascal, tu as utilisé le TPageExtControl, c'est un composant additionel, c'est interdit par le règlement, et de plus, je ne peux pas compiler ton code...

Remet un TPageControl...vite...

Avis aux amateurs de composants, PAS DE COMPOSANTS hors vcl de base !

[anapurna]

salut

Nous avons la un problème de définition:
Pour aller plus loin dans ta grille on va utiliser la méthode de 'couleurs"
c'est a dire une méthode d'hypothèses parfaitement maitrisée. Et donc doit-on considère que la méthode des couleurs est une méthode logiue
ou une méthode Brute force

En réalité les soldeurs par restriction ou contrainte (essai de tous les candidats possibles) utilisent la méthode des couleurs

En fait toutes les problemes sont solubles en n'utilisant que les couleurs
car couleur = hypothèse

Boris

appelé aussi coloring map
c'est l'équivalent du coloriage de la carte de France avec 4 couleur
il as été démontré que la théorie des graphe s'applique au problème du sudoku

@+ Phil

[anapurna]

salut

[EDIT]

Quelqu'un aurait-il des routines rusées pour inverser ou
pivoter de 90° une matrice: faire que les colonnes
deviennent rangées?
Merci
[\EDIT]

tu veut que les colonne devienne des ligne et inversement
le plus simple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
For L := low(Tab) to  High(Tab) do 
begin
   For C := low(Tab[L]) to  High(Tab[L]) do 
     Result[C,L] := Tab[L,C];
end;

@+ Phil

[FullSpeed]

Merci Anapurna mais ton code (efficace) c'est la methode traditionnelle
je cherche si nos matheux n'ont pas imaginer des cosinus de Log...

Pour les couleurs et hypothèses cela n'a rien a voir avec la methode
des graphes : il y a un problème de vocabulaire. On ne parle pas de la meme chose!

Si cela intéresse j'ai écrit une petite routine qui 'tasse' les grilles

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
931804075
090045780
800900450
475182369
 
000000070
030804780
891945455
475182369

On fait remonter les zéros et on garde le rang du révélé
Boris

[Pascal Fonteneau]

Felix a ecrit

Arg ! Pascal, tu as utilisé le TPageExtControl, c'est un composant additionel, c'est interdit par le règlement, et de plus, je ne peux pas compiler ton code...

Remet un TPageControl...vite...

Oups.... je corrige immédiatement.

Pascal

[Montor]

pour faire des tests rapide assembleur est inevitable il faut utiliser les bits d'un entier

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
var
lignes  :array[0..8] of integer;
colonnes:array[0..8] of integer;
subTabs :array[0..8] of integer;
sudoku  :array[0..80] of array[0..80] of integer;

initialization

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
   for i:=0 to 8 do
    begin
      lignes  [i]:=511;
      colonnes[i]:=511;
      subTabs [i]:=511;
    end;
   for i:=0 to 8 do
     for j:=0 to 8 do
     begin
          b:= (j div 3)+((i div 3)*3);
        if(sudoku[j,i]<>0) then
        begin
           ExcludeBit(lignes[i],sudoku[j,i]);
           ExcludeBit(subTabs[b],sudoku[j,i]);
        end ;
 
 
        if(sudoku[i,j]<>0) then
          ExcludeBit(colonnes[i],sudoku[i,j]);
 
     end ;
 
...

fonctions assembleur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
//bit a zéro
procedure ExcludeBit(var Bits:integer;Index: Integer);register;
asm
    DEC     EDX
    BTR     [EAX],EDX
end;
 
//premier bit a 1
function Firstidx(value:integer):integer; register;
 asm
    BSF EAX,EAX
    JZ      @exit
    INC     EAX
    RET
  @exit:
end;
 
//test si un bit est a 1
function _in(A,b : integer) : boolean ; register;
asm
  DEC  EDX
  BT EAX,EDX
  SETC AL
end ;

fonction de test pascal

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
//premier occurence 
function PremierOc(c,r,s:integer):integer;
begin
   result:= Firstidx(lignes[r] and colonnes[c]  and subTabs[s]);
end;
//Intersection 
function Intersec(c,r,s:integer):integer;
begin
   result:= lignes[r] and colonnes[c]  and subTabs[s];
end;

j'espere que le code ne sera pas supprimer

[anapurna]

salut

Merci Anapurna mais ton code (efficace) c'est la methode traditionnelle
je cherche si nos matheux n'ont pas imaginer des cosinus de Log...

genre un modulo 3 pour eviter de faire les 81 cases

Pour les couleurs et hypothèses cela n'a rien a voir avec la methode
des graphes : il y a un problème de vocabulaire. On ne parle pas de la meme chose!

fait une recherche sur "Sudoku Squares and Chromatic Polynomials"
tu comprendra peut etre la relation entre les couleurs ,les graphes et le sudoku

Si cela intéresse j'ai écrit une petite routine qui 'tasse' les grilles

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
931804075
090045780
800900450
475182369
 
000000070
030804780
891945455
475182369

On fait remonter les zéros et on garde le rang du révélé
Boris

ta matrice résultante n'est pas exact tu as perdu le premier 9

sinon il y as une possibilité d'utilisation des matrice appelée
"Diagonally Distinct Sudoku Squares"
il faut que je verifie quelque petit truc mais cela parait prometteur



@+ Phil