[Défi] Le Défi Delphi n°5 : Le Sudoku solver

**anapurna** · 02/07/2009, 12h56

salut

Envoyé par Montor

Code :

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

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

peut aussi s'ecrire

Code :

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

1
2
3
4
5
6
 
//premier occurence 
function PremierOc(c,r,s:integer):integer;
begin
   result:= Firstidx(Intersec(c,r,s));
end;

PS il est possible de jouer avec les and et les or les shl et shr pour decrementer tes valeurs

@+ Phil

**Montor** · 02/07/2009, 13h04

comme ca tu perds quelques us

**FullSpeed** · 02/07/2009, 19h33

Merci Mentor c'est exactement se que je cherchais: un autre algo

L' exemple pour la matrice je l'ai tapé a l'écran et j'ai defait
oublié un neuf
Promis elle fonctionne (si on en a besoin)

Merci
Boris (je me suis fait expliqué combien ca representait une
pico secondes :je confondais avec un picon....

)

**mick605** · 02/07/2009, 20h51

Salut a tous !

Je me posais la question sur l'utilité du X-Wing ... est ce que quelqu'un aurait sous la souris une grille complete ou il existerai un X Wing ? Toutes celles que j'ai (et j'en ai) n'en ont pas !

Merci

!

Edit : a c'est bon, j'en ai trouvé une !!
Bon, va falloir coder

!

**Montor** · 02/07/2009, 21h39

voici une procedure qui permet de recuperer la vitesse de cpu ca peut etre utile pour toi

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
 const
ID_BIT=$200000; // EFLAGS ID bit
 
function GetCPUSpeed: Double;
const
DelayTime = 500;
var
TimerHi, TimerLo: DWORD;
PriorityClass, Priority: Integer;
begin
try
PriorityClass := GetPriorityClass(GetCurrentProcess);
Priority := GetThreadPriority(GetCurrentThread);
 
SetPriorityClass(GetCurrentProcess, REALTIME_PRIORITY_CLASS);
SetThreadPriority(GetCurrentThread,THREAD_PRIORITY_TIME_CRITICAL);
 
Sleep(10);
asm 
dw 310Fh // rdtsc 
mov TimerLo, eax 
mov TimerHi, edx 
end;
Sleep(DelayTime); 
asm 
dw 310Fh // rdtsc 
sub eax, TimerLo 
sbb edx, TimerHi 
mov TimerLo, eax 
mov TimerHi, edx
end; 
 
SetThreadPriority(GetCurrentThread, Priority); 
SetPriorityClass(GetCurrentProcess, PriorityClass);
 
Result := TimerLo / (1000.0 * DelayTime); 
except end; 
end;
 
 
procedure TForm1.Button1Click(Sender: TObject);
var cpuspeed:string;
begin
cpuspeed:=Format('%f MHz', [GetCPUSpeed]);
edit1.text := cpuspeed;
end;

**Pascal Fonteneau** · 03/07/2009, 07h46

Sur ce site, il existe des grilles avec des exemples 'x-wings' etc...

http://www.mots-croises.ch/Manuels/Sudoku/

Pascal

**FullSpeed** · 03/07/2009, 08h09

Un bon programmeur n'utilise pas trop de "IF" ça brise la linéarité de l'automation

Tu fais quoi dans la vraie vie: prédicateur de branchements?

J'y vais moi aussi de ma routine ASM (dont je ne suis pas l'auteurr)

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
26
27
28
29
30
31
 
procedure FillMem32(var Buff; Size: Cardinal; Value: Cardinal);
asm
{    ->EAX    Pointer to destination  }
{      EDX    count  }
{      ECX    value  }
 
        PUSH    EDI
        PUSH    ESI
        MOV    EDI,EAX
        MOV    EAX, ECX
        MOV    ECX,EDX
        SAR    ECX,2
        JS      @@exit
        REP    STOSD
        MOV    ECX,EDX
        AND    ECX,3
        JZ      @@exit
        STOSB
        DEC    ECX
        JZ      @@exit
        SHR    EAX, 8
        STOSB
        DEC    ECX
        JZ      @@exit
        SHR    EAX, 8
        STOSB
@@exit:
        POP    ESI
        POP    EDI
end;

Comme son nom l'indique elle initialise une zone mémoire avec une vcaleur sur 32 bits. Par définition 4 fois plus rapide qu'un fillchar..
Pour initialiser lignes,colonnes...
elle accepte les longueurs qui ne sont pas modulo 8
Size est le nombre de byte pas d'int64
Boris

**mick605** · 03/07/2009, 14h38

Envoyé par Pascal Fonteneau

Sur ce site, il existe des grilles avec des exemples 'x-wings' etc...

http://www.mots-croises.ch/Manuels/Sudoku/

Pascal

Merci, c'est en fait sur ce site que je les ai trouvé les grilles

!

**Montor** · 03/07/2009, 20h55

Envoyé par FullSpeed

Avant de pouvoir attaquer une série il vous faudra AU MINIMUM
faire 9 hypothèses soit 5^9 (1 953 125) essais
Comment vous en rendre compte...

effectivement c'est impossible mais si un jour quelqu'un arrive à linéariser les grilles tu peux utiliser la recherche dichotomique.
cest terminer pour moi bonne chance

**Montor** · 03/07/2009, 23h04

mon code a trebucher sur ces grilles

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
000 000 000
000 390 280
040 021 093
600 070 900
900 502 006
005 060 001
180 250 030
064 018 000
000 000 000
 
100 007 090
030 020 008
009 600 500
005 300 900
010 080 002
600 004 000
300 000 010
040 000 007
007 000 300

mick tu dois integrer plisieus solveurs si tu veux gagner
je viens de trouver sur un jeu :
Pair
Triple
X wing
Swordfish
Multi
SolveByCell
SolveBySingleCan
SolveByLockedCan
SolveByRepeatCan
SolveByFishCan
SolveByMultiColor
SolveByLogic
bonne chance a vous tous

**mick605** · 04/07/2009, 00h46

Envoyé par Montor

mon code a trebucher sur ces grilles

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
000 000 000
000 390 280
040 021 093
600 070 900
900 502 006
005 060 001
180 250 030
064 018 000
000 000 000
 
100 007 090
030 020 008
009 600 500
005 300 900
010 080 002
600 004 000
300 000 010
040 000 007
007 000 300

Mon solveur résoud la premiere sans utiliser toutes ses techniques ...
Quand a la deuxieme, ca m'aurait (agréablement) étonné qu'un solveur logique la résolve ... c'est AI Escargot !!

Envoyé par Montor

mick tu dois integrer plisieus solveurs si tu veux gagner
je viens de trouver sur un jeu :
Pair .....................//fait
Triple...................//fait
X wing.................//en cours
Swordfish
Multi ....................????
SolveByCell............//fait
SolveBySingleCan....//fait
SolveByLockedCan......//fait
SolveByRepeatCan.......//fait
SolveByFishCan.............???
SolveByMultiColor............???
SolveByLogic..................???
bonne chance a vous tous

Quelles sont les techniques qui ont des points d'interrogation ??
Qu'entends tu par plusieurs solvers ?? Plusieurs techniques de résolution ? Si c'est cela, oui, c'est le cas

!!

**FullSpeed** · 04/07/2009, 09h00

Mick je te conseille ce logiciel
http://pgailhac.free.fr/index.html
Il utilise un certain nombre de techniques et a surtout des exemples de chaque .

Boris

**mick605** · 04/07/2009, 13h36

Envoyé par FullSpeed

Mick je te conseille ce logiciel
http://pgailhac.free.fr/index.html
Il utilise un certain nombre de techniques et a surtout des exemples de chaque .

Boris

Merci

**Kaféine** · 07/07/2009, 16h29

cool ce défi.

on peut faire un solver avec un algorithme génétique ou c'est la vitesse à tout prix?

**mick605** · 07/07/2009, 19h01

Non, ce n'est pas la vitesse qui compte ... (enfin, on veut la réponse dans l'heure ^^

)
Tu peux faire n'importe quel algo, et c'est meme le bienvenu ! Ca ne sera pas interressant si tout le monde a un brute force !

Bonne chance

**Aka Guymelef** · 08/07/2009, 08h23

Envoyé par Kaféine

cool ce défi.

on peut faire un solver avec un algorithme génétique ou c'est la vitesse à tout prix?

Les pré-requis ainsi que les critères de notation sont définis dans la page du défi. Et non la vitesse ne sera pas le seul critère déterminant, soyez créatif dans votre programme

.

**Félix Guillemot** · 12/07/2009, 17h03

Envoyé par Aka Guymelef

Les pré-requis ainsi que les critères de notation sont définis dans la page du défi. Et non la vitesse ne sera pas le seul critère déterminant, soyez créatif dans votre programme

.

Je confirme, ceci n'est pas un benchmark pour microprocesseurs ou un concours d'assembleur mais bien défi Delphi (= un jeu) dont les règles ont été clairement définies dès le départ.
Donc il est ouvert à tous, et toutes les idées sont les bienvenues.
Amusez vous bien

**FullSpeed** · 13/07/2009, 12h03

L'ASM fait partie de Delphi. On peut donc a priori s'en servir?
J'utilise une seule routine ASM de (3) trois instructions.(usage REP)
C'est permis?
Boris

**mick605** · 13/07/2009, 17h18

Envoyé par FullSpeed

L'ASM fait partie de Delphi. On peut donc a priori s'en servir?
J'utilise une seule routine ASM de (3) trois instructions.(usage REP)
C'est permis?
Boris

Ben ouais, bien sur. Ce qu'il voulait dire, c'est que le but n'est pas de coder en assembleur, pas que c'était interdit ...
Mais il parait que ca n'apporte guere d'améliorations ...

**FullSpeed** · 13/07/2009, 19h52

Cela apporte seulement si cela a besoin accéder a des techno non disponibles dans le langage Par exemple si tu veux utiliser le MMX ou les capacités SSE2 tu es obligé de passer en ASM. Mais pour faire un inttostr ou un Pos on peut aller plus vite en ASM mais c'est tellement plus agréable d'utiliser la RTL ou al:ors dans des optiques de vitesse pure ou les compilateurs sont generiques et ne savent pas se montrer astucieux comme un humain qui verra la particularité de la situation.
C'est pour cela que je dis pourquoi j'utilise de l'ASM je ne sais pas comment faire un xchange et un REP en Pascal.

Je pense avoir trouver une fonctionnalité sympa pour les juges.J'espère qu'ils aimeront! Tu t'en sors de ton solveur logique?. Moi je sais que c'était pas la programmation des méthodes qui m'avaient arrêté mais leur enchainement pour faire un produit complet

Bon je retourne à mon code
Boris

[Défi] Le Défi Delphi n°5 : Le Sudoku solver

Delphi

Discussions similaires

Partager

Partager