「騎士の巡回問題」のプログラムを作るには？ (ID:10015)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文

こういう、仕事に関係ないプログラム、好きです^^;
頭の体操になる(笑)

スタテツさん、これは巡回セールスマン問題ですよ。
複数ある都市を回る、最短ルートを探すやつですよね。

騎士巡回問題は、単純に総当たりでいいのでは？
# 他にアルゴリズムを知らない^^;

例えば、8x8・・・だとでかいので^^;5x5の盤を想定します。
騎士は、最大２つのマスを移動しますよね。横に１，縦に２とか。つまり、盤をはみ出さないように、以下のようなデータを用意します。

1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1 1
1 1 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
これで、開始地点を(2,2)として、移動パターンごとに試し、移動したら０以外の数値を入れて、０でなければ他の移動箇所を試す、という総当たりになります。

こんな感じ。
・盤面の大きさを定義
const
  N = 5; // 5以上に解あり。ただ、６以上はめちゃ遅い^^;

・TForm1にButton1とMemo1をはる。
・TForm1のPrivateに、以下の変数と関数を宣言。

board: array[0..N + 3, 0..N + 3] of integer;
    count: integer;
    ans: integer;

procedure Move(x, y: integer);
    procedure printboard;

・Button1のOnClickイベントを定義

procedure TForm1.Button1Click(Sender: TObject);
var
  i, j: integer;
begin
  for i := 0 to N + 3 do
    for j := 0 to N + 3 do board[i, j] := 1;
      for i := 2 to N + 1 do
        for j := 2 to N + 1 do board[i, j] := 0;
  count := 0;
  ans := 0;
  Move(2, 2);
end;

自前の関数を定義。
procedure TForm1.Move(x, y: integer);
const
  dx: array[0..7] of integer=(2, 1,-1,-2,-2,-1, 1, 2);
  dy: array[0..7] of integer=(1, 2, 2, 1,-1,-2,-2,-1);
var
  i: integer;
begin
  if board[x, y] <> 0 then Exit; (* すでに訪れた *)
  Inc(count);
  board[x, y] := count;
  if count = N * N then
    printboard  (* 完成 *)
  else
    for i := 0 to 7 do Move(x + dx[i], y + dy[i]);
  board[x, y] := 0;
  Dec(count);
end;

procedure TForm1.printboard;
var
  i, j: integer;
  s: String;
begin
  Inc(ans);
  Editor1.Lines.Add(Format('解その%d', [ans]));
  for i := 2 to N + 1 do
  begin
    s := '';
    for j := 2 to N + 1 do s := s + Format('%3d', [board[i, j]]);
    Editor1.Lines.Add(s);
  end;
end;

参考は、「C言語によるアルゴリズム辞典」です。

←解決時は質問者本人がここをチェックしてください。

戻る