国际象棋中马的遍历问题

柴米油盐

xixi

pandalcg

小学计算机比赛的一道题, 用深度优先搜索回溯, 每一步走边优先的方法.

home_king

最初由 pandalcg 发表
小学计算机比赛的一道题, 用深度优先搜索回溯, 每一步走边优先的方法.

请看上面的我的帖子，已经有说明——图的深度搜索。

ps：不要说得这么玄，如果小学生有这么厉害的话，那我们国家就不至于推广一个Linux都如此艰难了。。。。。不要说小学生，大学生的计算机水平都是普遍低下的。。。只会上网，聊QQ

BBDD

这问题用递归比较方便。
程序我已经编出来了，只不过用perl比较慢。算5X5的棋盘还行：

[php]
#!/usr/bin/perl -w
use strict;

#初始化棋盘，未走过的位置为0，走过的为1。
my $size = 5;             #设置棋盘大小
my ($row, $col) = ($size - 1, $size - 1);

my @chess_table;

for my $i (0..$row) {
  for my $j (0..$col) {
    $chess_table[$i][$j] = 0;
  }
}

#起始位置
my ($startx, $starty) = (0, 0);

my $result;

if ( $result = horse_move( $startx, $starty, @chess_table ) ) {
  print "The Path is:\n$result\n";
} else {
  print "No Result!\n";
}

print "\n\nAll done!\n";

###############################

sub horse_move {
  my ($x, $y, @table) = @_;

  my @new_table = map { [ @$_ ] } @table;           #复制棋盘
  $new_table[$x][$y] = 1;                            #设置走过的点为1

  return "($x, $y)" if ( all_done( @new_table ) );  #如果棋盘上的所有点都已走过则结束递归

  # 马可以走的八个位置
  my @choices = ( [$x - 2, $y - 1],
                  [$x - 2, $y + 1],
                  [$x + 2, $y - 1],
                  [$x + 2, $y + 1],
                  [$x + 1, $y - 2],
                  [$x - 1, $y - 2],
                  [$x + 1, $y + 2],
                  [$x - 1, $y + 2] );

  for my $i (0..$#choices) {
    my ($nx, $ny) = @{$choices[$i]};

    next if ( $nx < 0 or $nx > $row or $ny < 0 or $ny > $col );  #判断($nx, $ny)是否在棋盘之内
    next if ( $new_table[$nx][$ny] );                            #判断($nx, $ny)是否已走

    my $result = horse_move( $nx, $ny, @new_table );
    return "($x, $y) -> $result" if ( $result );
  }
  
  return 0;                  #如果八个位置都没有结果则返回0
}

sub all_done {
  my (@tab) = @_;

  for my $i ( 0..$row ) {
    for my $j ( 0..$col ) {
      return 0 unless ( $tab[$i][$j] );        #若存在未访问过的点，则返回0
    }
  }
  return 1;
}
[/php]

结果：

1. 
   
2. The Path is:
   
3. (0, 0) -> (2, 1) -> (0, 2) -> (1, 0) -> (3, 1) ->
   
4. (4, 3) -> (2, 2) -> (1, 4) -> (3, 3) -> (4, 1) ->
   
5. (2, 0) -> (0, 1) -> (1, 3) -> (3, 4) -> (4, 2) ->
   
6. (3, 0) -> (1, 1) -> (0, 3) -> (2, 4) -> (1, 2) ->
   
7. (0, 4) -> (2, 3) -> (4, 4) -> (3, 2) -> (4, 0)
   

复制代码

BBDD

6X6的棋盘也有结果了。

1. 
   
2. The Path is:
   
3. (0, 0) -> (2, 1) -> (0, 2) -> (2, 3) -> (0, 4) -> (2, 5) ->
   
4. (4, 4) -> (5, 2) -> (4, 0) -> (3, 2) -> (1, 1) -> (3, 0) ->
   
5. (5, 1) -> (4, 3) -> (5, 5) -> (3, 4) -> (1, 5) -> (0, 3) ->
   
6. (2, 2) -> (0, 1) -> (1, 3) -> (0, 5) -> (2, 4) -> (4, 5) ->
   
7. (5, 3) -> (4, 1) -> (2, 0) -> (1, 2) -> (3, 3) -> (1, 4) ->
   
8. (3, 5) -> (5, 4) -> (4, 2) -> (5, 0) -> (3, 1) -> (1, 0)
   

复制代码

BBDD

优化一下算法：
[php]
#!/usr/bin/perl -w
use strict;

#初始化棋盘，未走过的位置为0，走过的为1。
my $size = 5;   #设置棋盘大小
my ($row, $col) = ($size - 1, $size - 1);

my @chess_table;

for my $i (0..$row) {
  for my $j (0..$col) {
    $chess_table[$i][$j] = 0;
  }
}

#起始位置
my ($startx, $starty) = (0, 0);

my $result;
my $pt_left = $size * $size;        #剩下未走的格数

if ( $result = horse_move( $startx, $starty, $pt_left, @chess_table ) ) {
  print "The Path is:\n$result\n";
} else {
  print "No Result!\n";
}

print "\n\nAll done!\n";

###############################

sub horse_move {
  my ($x, $y, $pt_left, @table) = @_;

  $table[$x][$y] = 1;                                    #设置走过的点为1
  $pt_left--;                                       #剩下的格数减一

  return "($x, $y)" if ( $pt_left == 0 );           #如果棋盘上的所有点都已走过则结束递归

  # 马可以走的八个位置
  my @choices = ( [$x - 2, $y - 1],
                  [$x - 2, $y + 1],
                  [$x + 2, $y - 1],
                  [$x + 2, $y + 1],
                  [$x + 1, $y - 2],
                  [$x - 1, $y - 2],
                  [$x + 1, $y + 2],
                  [$x - 1, $y + 2] );

  for my $i (0..$#choices) {
    my ($nx, $ny) = @{$choices[$i]};

    next if ( $nx < 0 or $nx > $row or $ny < 0 or $ny > $col );  #判断($nx, $ny)是否在棋盘之内
    next if ( $table[$nx][$ny] );                            #判断($nx, $ny)是否已走
   
    my $result = horse_move( $nx, $ny, $pt_left, @table );
    return "($x, $y) -> $result" if ( $result );      #如果有结果则直接返回
  }
  #如果八个位置都没有结果……
  $table[$x][$y] = 0;                            #恢复($x, $y)为未走状态
  return 0;                                    #返回0               
}
[/php]

BBDD

最终版：
[php]
#!/usr/bin/perl -w
use strict;

my $SIZE = 6;
my ($row, $col) = ( $SIZE - 1, $SIZE - 1 );

my @board;

my @rules = ([-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]);
my $count = 0;

my $DONE = $SIZE * $SIZE;

my ($x, $y) = (0, 0);

for my $i (0..$row) {
  for my $j (0..$col) {
    $board[$i][$j] = 0;
  }
}

print "Start at ($x, $y)...\n";
horse( 1, $x, $y );

################

sub horse {
  my ($step, $x, $y) = @_;
  return if ( $x < 0 or $x > $row or $y < 0 or $y > $col or $board[$x][$y] > 0);
  $board[$x][$y] = $step;
  if ( $step == $DONE ) {
    printf "Result %d :\n", ++$count;
    for my $i (0..$row) {
      for my $j (0..$col) {
        print "$board[$i][$j]\t";
      }
      print "\n";
    }
  } else {
    for my $i (0..$#rules) {
      horse( $step + 1, $x + $rules[$i][0], $y + $rules[$i][1] );
    }
  }
  $board[$x][$y] = 0;
}
[/php]