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

名前

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

本文

騎士巡回の問題は、
その次の分岐先（２手先）の可能分岐数が最も少ないところを選択していけば解が簡単に見つかるそうです。

上述のソースは全部の解を羅列できますが、とりあえず１種類だけすばやく求めるにはこのアルゴリズムを使ってください。
50ｘ50でも一瞬で求まります。

以下、長いですが・・・・
（再帰はわけがわからなくなるので使っていません）

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;
const
  N = 50; // 5以上に解あり。
  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);

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private 宣言 }
    board: array[0..N + 3, 0..N + 3] of integer;
    count: integer;
    ans, Flag : integer;
    TestCount :Integer;
    Gx,Gy :Integer;
    procedure Move(x, y: integer);
    procedure Draw(x, y: integer);
    procedure Search(x, y: integer);
    procedure Test(x, y: integer);
  public
    { Public 宣言 }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
  i, j: integer;
  t1,t2: Longint;
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;
  Flag := 0;
  ans := 0;
  Gx:=2;Gy:=2;
  board[Gx, Gy] := 1;
  Move(Gx, Gy);

t1 := GetTickCount;
  for i := 0 to N*N-2 do
  begin
    Search(Gx, Gy);
    Move(Gx, Gy);
  end;
  t2 := GetTickCount;

Memo1.Lines.add(FloattoStr((t2-t1)/1000)+'s');

end;

procedure TForm1.Move(x, y: integer);
begin
  Inc(count);
  board[x, y] := count;
  Draw(x, y);

end;

procedure TForm1.Search(x, y: integer);
var
  i,j,min: integer;
  TCTest :array[0..7] of integer;
begin

for j := 0 to 7 do
    begin

if board[x+ dx[j] , y+ dy[j] ] = 0 then //未訪なら
      begin                                   //分岐先範囲をチェック
        TestCount := 0;
        for i := 0 to 7 do
            Test(x + dx[i]+ dx[j],  y + dy[i]+ dy[j]);

TCTest[j] := TestCount;              //分岐数を記憶
      end
      else
      begin
        TCTest[j] :=255;
      end;

end;

min := 0;
    for i := 1 to 7 do                       //最も分岐数が少ないものを選ぶ
      if TCTest[min] > TCTest[i] then min :=i;

Gx:= x + dx[min];
    Gy:= y + dy[min];

end;

procedure TForm1.Test(x, y: integer);
begin

if board[x , y ] = 0 then Inc(TestCount); (* 未訪 *)

end;

procedure TForm1.Draw(x, y: integer);
var
x1,y1,x2,y2,offset: Integer;

begin
  offset := round(50/N);
  y1 := round(x*200/N);
  x1 := round(y*200/N);
  y2 := round((x+1)*200/N);
  x2 := round((y+1)*200/N);

Form1.Canvas.Rectangle(x1,y1,x2,y2);
  Form1.Canvas.TextOut(x1 + offset,y1 + offset,IntToStr(count));

end;

end.

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

戻る