牵着老婆满街逛

完整的程序代码可以从http://www2.cnblogs.com/Files/zhenyulu/HRD.rar下载

九、 代码设计

在看完了解题过程后，下面来看一看具体的代码设计方案：

我们首先从Core开始，在Core.dll里面定义了系统所需的最基本的数据类型以及相关的接口。其中枚举ChessmanType与MoveMethod分别定义了棋子的类型以及棋子移动的方法。

public enum ChessmanType
{
  Blank = 0,
  Solider = 1,
  VChessman = 2,
  HChessman = 3,
  General = 99
}

public enum MoveMethod
{
  Up, 
  Down, 
  Left, 
  Right, 
  Up2, 
  Down2, 
  Left2, 
  Right2, 
  Turning,
  Nothingness    //没有任何移动
}

ChessStep定义了棋局中的"一步"棋。包括当前棋盘布局的整数表示、移动了哪一个棋子以及如何移动。当华容道自动解题程序完成后，将返回一个ChessStep[]数组，记录每一步的走法。我们可以通过实现IResultHandler接口的"HandleResult (ChessStep[] steps)"方法来达到这一目的。IResultHandler接口将在后面加以介绍。

public struct ChessStep
{
  public short chessmanNum;
  public MoveMethod moveMethod;
  public int layout;
}

Position与BlankPosition是两个结构"structure"，用来记录棋子的位置以及某一棋盘上空格的位置。BlankPosition中有一IsBlank(int x, int y)方法，用来判断坐标为(x,y)的点是否是空格。

public struct Position
{
  public int x;
  public int y;

  public Position(int x, int y)
  {
    this.x = x;
    this.y = y;
  }
}

public struct BlankPosition
{
  public Position Pos1;
  public Position Pos2;
    
  public BlankPosition(Position pos1, Position pos2)
  {
    this.Pos1 = pos1;
    this.Pos2 = pos2;
  }

  public bool IsBlank(int x, int y)
  {
    if( x == Pos1.x && y == Pos1.y)
      return true;
    if( x == Pos2.x && y == Pos2.y)
      return true;
      return false;
  }
}

之所以选择使用结构而不是类是因为struct是值类型的，而class是引用类型。在本程序中，struct要比class更有效率。关于struct与class的区别在这里就不再详细讨论了。我们看下面一段程序：

Position P1 = new Position(0,0);
Position P2;
P2 = P1;

P2经过赋值后，P2.x与P2.y都与P1相同，并且这种赋值不是"引用"赋值，修改P2中x、y的值并不会影响P1中x、y的值。

HRD.Core命名空间下除了这些基本类型的定义外，还定义了一系列接口，主要是用来达到解耦目的。在上篇文章中，我们看到了TreeLinkedList、CircularLinkedList以及AVLTree之间如何协作工作，但在实际代码设计中，这将带来严重的耦合问题。组件与组件之间联系过于紧密，造成无法有效的剥离。为此，程序在设计时引入了"中介者"模式，设计了一个Mediator，所有组件仅与Mediator打交道，这样耦合便被"松动"了。

Mediator的定义如下：

public class Mediator
{
  private IAVLTree _avlTree;
  private ICircularList _circleList;
  private ITreeList _treeList;
  private IResultHandler _resultHandler;
  
  …………

}

其中IAVLTree、ICircularList、ITreeList便是参与运算的三种数据结构。其具体定义可以参考具体的程序源代码。（可以参考http://www2.cnblogs.com/zhenyulu/archive/2005/02/03/101426.html里面的代码，但不是最终版本，可能会与本文有所出入）。

这里还有一个接口定义，就是IResultHandler接口。刚才已经提到过。我们可以将一个实现了该接口的对象传递给Mediator对象，这样，当系统运算完成后便会调用IResultHandler中的特定方法，将结果回传。

public interface IResultHandler
{
  void HandleResult(ChessStep[] steps);
  void HandleInfo(int currentStep);
}

IResultHandler定义了两个方法HandleResult与HandleInfo。HandleResult用来处理程序产生的结果，结果以ChessStep数组的形式传入。HandleInfo可以被用来处理程序运算过程中的一些中间信息。这里我只提供了一个信息，那就是当前搜索层次是什么。它通过currentStep参数传入。如果需要，用户可以重新定义该接口以获取更多的信息（例如搜索了多少个节点等）。IResultHandler接口的具体使用方法可以参考源代码中WinHRD或ConsoleHRD中的实现。

HRD.Core命名空间下还定义了Layout以及Chessman，此外还有一个CallBackDelegate的定义，这些将在后续的文章中再加以介绍。

十、 Chessman的设计

整个程序中一个非常关键的环节就是Chessman（棋子）的设计以及Layout（棋盘布局）的设计。这次先说说Chessman的设计。

由于我的程序只针对10子布局，所以一个Layout应当包括10个棋子，分别归属于General、HChessman、VChessman与Soldier。下面是抽象Chessman类的部分定义：

public abstract class Chessman
{
  protected Position _position;

  protected Position _newPosition = new Position(-1,-1);
  protected BlankPosition _newBlankPosition = new BlankPosition();

  // 构造函数
  public Chessman(Position position)
  {
    this._position = position;
  }

  // ………… 此处省略一些属性的定义

  public virtual ChessmanType chessmanType
  {
    get 
    {
      return ChessmanType.Blank;
    }
  }

  public abstract void CheckAvailableSteps(BlankPosition _blankPosition, CallBackDelegate _callback);
}

在这个定义里面我们可以看到以下几项：_position，记录了当前棋子在棋盘中的位置。_newPosition、_newBlankPosition，当移动棋子后，棋子的新位置以及空格的新位置。关于这点在后面有进一步的说明。只读chessmanType属性，标识当前棋子类型。

还有一个抽象方法：CheckAvailableSteps是Chessman的核心。在方法中包含了一个CallBackDelegate类型参数，是一个回调函数的委派。程序的运行机制是：CircularLinkedList调用Layout的CheckAvailableSteps方法，Layout再依次调用其每个包含棋子的CheckAvailableSteps方法，并提供一个回调函数（就是Layout的EncapsulateChessStep方法）。一旦棋子有可行的走法，就回调该函数，传入新的棋子位置以及新的空格位置，并以此产生一新Layout。然后的步骤就是将此新Layout纳入CircularLinkedList并检验AVLTree是否有重复值等等，大家可以参考（《华容道与数据结构 (4) 》）中的内容。

这理有一点需要明白的就是棋子的移动问题。其实某个棋子能否移动以及如何移动仅与当前空格位置有关。如图：

所以，我们仅需知道空格在什么位置便可以计算出下一步的移动方法。另外，棋子移动后，我们只需要回传该棋子的新位置以及空格的新位置就可以在原有布局的基础上产生出一新的可行布局。当然此布局还要经过AVLTree的检验才可以被加入CircularLinkedList以及TreeLinkedList当中。

举例来说，在HChessman类中，我们会看到若干私有方法如下：

private bool CanMoveUp(BlankPosition _blankPosition)
{
  if(_blankPosition.IsBlank(_position.x , _position.y - 1) && 
     _blankPosition.IsBlank(_position.x + 1, _position.y - 1))
  {
    // 设置棋子新位置
    _newPosition.x = _position.x;
    _newPosition.y = _position.y - 1;

    // 设置新的空白位置
    _newBlankPosition.Pos1 = _position;
    _newBlankPosition.Pos2.x = _position.x + 1;
    _newBlankPosition.Pos2.y = _position.y;
        
    return true;
  }
  return false;
}

该段代码判断当前棋子是否可以向上移动，唯一的判别依据就是空格的位置，也就是传入的_blankPosition参数。如果可以移动的化，则给_newPosition与_newBlankPosition赋值移动后棋子的位置与空格的位置。在HChessman的CheckAvailableSteps方法中，我们可以看到如下代码：

public override void CheckAvailableSteps
(BlankPosition _blankPosition, CallBackDelegate _callback)
{
  if(CanMoveUp(_blankPosition))
    _callback(_newPosition, _newBlankPosition, MoveMethod.Up);

  …………

}

上面代码的意思是说，如果棋子可以向上移动的化，则回调_callback（也就是Layout的EncapsulateChessStep方法），传入三个参数：棋子新位置、新空格位置以及当前移动方法。在EncapsulateChessStep方法中将根据这些信息生成新的棋盘布局Layout。Layout的EncapsulateChessStep方法定义如下：（经部分简化）

private void EncapsulateChessStep
  (Position newPosition, BlankPosition newBlankPosition, MoveMethod mm)
{
  Layout l = _mediator.AllocateLayout();
  
  // 生成新布局
  for(int i = 0; i<10; i++)
  {
    if(this.chessmen[i] == this.sortedChessmen[_current])
    {
      l.chessmen[i].position = newPosition;
      l.blankPosition = newBlankPosition;
    }
    else
    {
      l.chessmen[i].position = this.chessmen[i].position;
    }
  }

  // 初始化新布局
  l.InitLayoutMap();

  // 初始化当前移动"步法"
  ChessStep cs = new ChessStep();
  cs.layout = l.ToInt();
  cs.moveMethod = mm;

  if(sortedChessmen[_current].chessmanType == ChessmanType.General)
    cs.chessmanNum = 99;
  else
    cs.chessmanNum = (short)chessmanNum;

  // 将封装好的ChessStep发送给mediator作进一步处理
  if(l.IsFinished)
  {
    _gotTheAnswer = true;
    _mediator.Finished(cs);
  }
  else
    _mediator.CheckStep(cs);
}

在这段程序中，首先通过中介者_mediator从CircularLinkedList当中分配一可用Layout。

  Layout l = _mediator.AllocateLayout();  

然后将当前布局的10个棋子复制过去，在这里，注意被移动的棋子要复制其新位置，并用新的空格位置初始化新布局。

  // 生成新布局
  for(int i = 0; i<10; i++</