Itinéraire du Cavalier

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.

Signaler un problème

Roland Chastain

Rédacteur/Modérateur

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;

anapurna

Expert confirmé

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;