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

Version imprimable

Voir 40 message(s) de cette discussion en une page

salut

Citation:

Envoyé par Montor

Code:

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:

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

02/07/2009, 13h04
Montor

comme ca tu perds quelques us;)
02/07/2009, 19h33
FullSpeed

ASM

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....:lol:)
02/07/2009, 20h51
mick605

Salut a tous ! :D

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 :mrgreen: !

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

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

Code:

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;

03/07/2009, 07h46
Pascal Fonteneau

Grille avec techniques particulières

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

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

Pascal

Citation:

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:

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

03/07/2009, 14h38
mick605

Citation:

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 ;) !
03/07/2009, 20h55
Montor

Citation:

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

mon code a trebucher sur ces grilles
Code:

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

Citation:
Envoyé par Montor
mon code a trebucher sur ces grilles
Code:

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 !!

Citation:

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 ;) !!

04/07/2009, 09h00
FullSpeed

Examples

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
04/07/2009, 13h36
mick605

Citation:

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 :ccool:
07/07/2009, 16h29
Kaféine

cool ce défi.

on peut faire un solver avec un algorithme génétique ou c'est la vitesse à tout prix?
07/07/2009, 19h01
mick605

Non, ce n'est pas la vitesse qui compte ... (enfin, on veut la réponse dans l'heure ^^ :D )
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 ;)
08/07/2009, 08h23
Aka Guymelef

Citation:

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 :ccool:.
12/07/2009, 17h03
Félix Guillemot

Citation:

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 :ccool:.

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 :ccool:
13/07/2009, 12h03
FullSpeed

ASM

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
13/07/2009, 17h18
mick605

Citation:

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 ... :ccool:
13/07/2009, 19h52
FullSpeed

ASM

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

Voir 40 message(s) de cette discussion en une page