马踏棋盘

马踏棋盘问题，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。

#include <tr1/tuple>
#include <cstdio>

template <int width, int height>
struct chess
{
    static const int x_[8];
    static const int y_[8];

    int nodelinks_[width * height];
    int cat(int x, int y) const { return nodelinks_[x + width * y]; }
    int& at(int x, int y) { return nodelinks_[x + width * y]; }

    chess();

    void go(int x, int y)
    {
        for (int i = 0; i < 8; ++i)
        {
            int a = x + x_[i], b = y + y_[i];
            if (a >= 0 && b >= 0 && a < width && b < height && cat(a,b) > 0)
                at(a,b) -= 1;
        }
        static int number = 0;
        at(x,y) = --number;
    }

    std::pair<int, int> next(int x, int y) const
    {
        int j = 0;
        for (int i = 0, v = 8; i < 8; ++i)
        {
            int a = x + x_[i], b = y + y_[i];
            if (a >= 0 && b >= 0 && a < width && b < height)
                if (cat(a,b) > 0 && cat(a,b) < v)
                    j = i, v = cat(a,b);
        }
        return std::make_pair(x + x_[j], y + y_[j]);
    }

    void print() const
    {
        for (int x = 0; x < width; ++x)
        {
            for (int y = 0; y < height; ++y)
                printf("%3d ", cat(x,y));
            puts("");
        }
    }
};

template <int width, int height>
chess<width, height>::chess()
{
    const int X = width - 1;
    const int Y = height - 1;
    for (int x = 2; x < width-2; ++x)
        for (int y = 2; y < height-2; ++y)
            at(x,y) = 8;
    for (int x = 2; x < width-2; ++x)
    {
        at(x,1) = at(x,Y-1) = 6;
        at(x,0) = at(x,Y) = 4;
    }
    for (int y = 2; y < height-2; ++y)
    {
        at(1,y) = at(X-1,y) = 6;
        at(0,y) = at(X,y) = 4;
    }
    at(0,0) = at(X,0) = at(0,Y) = at(X,Y)= 2;
    at(1,1) = at(X-1,1) = at(1,Y-1) = at(X-1,Y-1)= 4;
    at(0,1) = at(0,Y-1) = at(1,0) = at(X-1,0) = at(X,1) = at(X,Y-1) = at(X-1,Y) = at(1,Y) = 3;
}

template <int width, int height> const int chess<width, height>::x_[] = { -1, -1,  1, 1, -2, -2,  2, 2 };
template <int width, int height> const int chess<width, height>::y_[] = { -2,  2, -2, 2, -1,  1, -1, 1 };


////
namespace tr1 = std::tr1;

int main(int argc, char* argv[])
{
    chess<8, 8> tab;
    int x = 0, y = 0;
    tab.go(x, y);
    for (int i = 1; i < 64; ++i)
    {
        tr1::tie(x, y) = tab.next(x, y);
        tab.go(x, y);
    }
    tab.print();
}



#if 0
 -1 -16 -59 -34  -3 -18 -21 -36 
-58 -33  -2 -17 -60 -35  -4 -19 
-15 -54 -57 -62 -43 -20 -37 -22 
-32 -63 -46 -53 -56 -61 -42  -5 
-49 -14 -55   0 -47 -44 -23 -38 
-28 -31 -48 -45 -52 -41  -6  -9 
-13 -50 -29 -26 -11  -8 -39 -24 
-30 -27 -12 -51 -40 -25 -10  -7 


  0   1   2   3   4   5   6   7
0 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
1 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
2 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
3 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
4 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
5 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
6 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
7 +---+---+---+---+---+---+---+

      @---+---@
      |   |   |
  @---+---+---+---@
  |   |   |   |   |
  +---+---@---+---+
  |   |   |   |   |
  @---+---+---+---@
      |   |   |
      @---+---@
#endif