Itinéraire du Cavalier

Présentation
L'itinéraire du Cavalier.

Démonstration d'un algorithme pour trouver un chemin passant sur toutes les cases du damier, sans jamais passer deux fois sur la même case. Adapté d'un script Lua.

https://rosettacode.org/wiki/Knight%27s_tour#Lua

Exemple d'utilisation de la bibliothèque Cairo.
Téléchargement
Compatibilité
Windows
1  0 
Téléchargé 10 fois Voir les 4 commentaires
Détails
Catégories : Maths et algorithmes
Avatar de Roland Chastain
Rédacteur / Modérateur
Voir tous les téléchargements de l'auteur
Licence : Non renseignée
Date de mise en ligne : 25 août 2016




Avatar de Roland Chastain Roland Chastain - Rédacteur/Modérateur https://www.developpez.com
le 25/08/2016 à 13:10
Avec le dessin des cases, c'est mieux.

Code : Sélectionner tout
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
48
49
50
51
52
53
54
55
56
57
58
procedure TForm1.DrawPath(const aPath: TVectorArray);
var
  surface: pcairo_surface_t;
  cr: pcairo_t;
  x, y: integer;
  i1, i2: integer;
  w, h: integer;
begin
  w := PaintBox1.Width;
  h := PaintBox1.Height;

  surface := cairo_win32_surface_create_with_dib(CAIRO_FORMAT_ARGB32, w, h);
  cr := cairo_create(surface);

  cairo_translate(cr, 0, h);
  cairo_scale(cr, w, -h);

  cairo_set_source_rgb(cr, 0.9, 0.9, 0.9);
  cairo_paint(cr);

   for x := 1 to 8 do for y := 1 to 8 do
    if (x + y) mod 2 = 0 then
    begin
      cairo_set_source_rgb(cr, 0.7, 0.7, 0.7);
      cairo_rectangle(cr, Pred(x) / 8, Pred(y) / 8, 1 / 8, 1 / 8);
      cairo_fill(cr);
    end;

  cairo_set_line_cap(cr, CAIRO_LINE_CAP_ROUND);
  cairo_set_line_width(cr, 1 / 200);

  cairo_set_source_rgb(cr, 0.1, 0.1, 0.1);

  for i2 := 1 to High(aPath) do
  begin
    i1 := Pred(i2);
    cairo_move_to(cr, aPath[i1].x / 8 - 1 / 16, aPath[i1].y / 8 - 1 / 16);
    cairo_line_to(cr, aPath[i2].x / 8 - 1 / 16, aPath[i2].y / 8 - 1 / 16);
  end;

  cairo_stroke(cr);

  cairo_destroy(cr);

  BitBlt(
    PaintBox1.Canvas.Handle,
    0,
    0,
    w,
    h,
    cairo_win32_surface_get_dc(surface),
    0,
    0,
    SRCCOPY
  );

  cairo_surface_destroy(surface);
end;
Avatar de anapurna anapurna - Expert confirmé https://www.developpez.com
le 25/08/2016 à 15:28
salut

pour l'initialisation de ton board
tu peut écrire FillChar(board,x*y*SizeOf(integer),UNVISITED);
plutôt que d'utiliser les boucles

ton tableau de moves tu aurais très bien pu l’écrire comme ceci

Code : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
 MOVES: array[1..8,1..2] of integer = (
    (+1,-2),
    (+2,-1),
    (+2,+1),
    (+1,+2),
    (-1,+2),
    (-2,+1),
    (-2,-1),
    (-1,-2)
  );

j'aurais fait quelque amelioration dans le DrawPath

Code : Sélectionner tout
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
procedure TForm1.DrawPath(const aPath: TVectorArray);
var
 coef1,Coef2 : ...
begin
   ...
  Coef1 := 1/8;
  Coef2 := 1/16; 
   for x := 1 to 8 do
    for y := 1 to 8 do
    if (x + y) mod 2 = 0 then
    begin
      cairo_set_source_rgb(cr, 0.7, 0.7, 0.7);
      cairo_rectangle(cr, Pred(x) / 8, Pred(y) / 8, Coef1,Coef1);
      cairo_fill(cr);
    end;
 ...

  for i2 := 1 to High(aPath) do
  begin
    i1 := Pred(i2);
    cairo_move_to(cr, aPath[i1].x / 8 - Coef2, aPath[i1].y / 8 - Coef2);
    cairo_line_to(cr, aPath[i2].x / 8 - Coef2, aPath[i2].y / 8 - Coef2);
  end;
 
  ...
end;
sinon c'est intéressant
Avatar de Roland Chastain Roland Chastain - Rédacteur/Modérateur https://www.developpez.com
le 25/08/2016 à 18:15
@anapurna

Merci pour le coup d'œil et les suggestions.
Avatar de Roland Chastain Roland Chastain - Rédacteur/Modérateur https://www.developpez.com
le 25/08/2016 à 20:31
Ajouté une version Lazarus.

 
Developpez.com décline toute responsabilité quant à l'utilisation des différents éléments téléchargés.