Ход конем

[msn]

Подскажите алгоритм заполнения щахматной доски таким образом как ходит шахматный конь.
спасибо.

[AiK]

Он прост пишешь рекурсивную функцию:
Функция попытка следующего хода
пока ход был удачным или нет других возможных ходов повторять
выбрать следующий ход
1) если ход удачный записать ход; если доска не заполнена (< 64 ходов) попытка следующего хода
2) иначе стереть предыдущий ход

[LAngel]

интересная задачка... описал вышеописанный алгоритм в дельфи:

Код: Выделить всё

procedure FillIt;
var
  cells: array[0..7, 0..7] of Integer;

  procedure DrawCells(N, M: Integer);
  var
    i, j: Integer;
  begin
    for i := 0 to 7 do
      for j := 0 to 7 do
        if cells[i, j] = 0
        then Form1.StringGrid1.Cells[i, j] := ''
        else Form1.StringGrid1.Cells[i, j] := IntToStr(cells[i, j]);

    Form1.Label1.Caption := IntToStr(N);
    Form1.Label2.Caption := IntToStr(M);
  end;

  function IsMoveIsPosible(X, Y: Integer; Move: Integer): Boolean;
  begin
    Result :=
      (X+moves[Move].X >= 0) and (X+moves[Move].X < 8) and
      (Y+moves[Move].Y >= 0) and (Y+moves[Move].Y < 8);
    if Result then Result := Cells[X+moves[Move].X, Y+moves[Move].Y] = 0;
  end;

  procedure FillFromPoint(X, Y: Integer; var N: Integer; M: Integer; var stop: Boolean);
  var i, p: Integer;
  begin
    stop := M = 64;
    Cells[x, y] := M;
    p :=StrToInt(Form1.Label2.Caption);
    if M > P then begin
      Form1.Label1.Caption := IntToStr(N);
      Form1.Label2.Caption := IntToStr(M);
      DrawCells(N, M);
      Application.ProcessMessages;
    end;
    inc(N); inc(M);
    For i := 1 to 8 do
    begin
      if stop then exit;
      if IsMoveIsPosible(x, y, i) then FillFromPoint(X+moves[i].x, Y+moves[i].y, N, M, stop);
    end;
    Cells[x, y] := 0;
  end;
var
  i, j: Integer;
  stop: Boolean;
begin
  For i := 0 to 7 do
    For j := 0 to 7 do
      Cells[i,j] := 0;
  i := 1; stop := False;
  FillFromPoint(0, 0, i, 1, stop);
  ShowMessage('ok!');
end;

первое совпадение, т.е. полное заполнение происходит на 8 250 733 проверке.