C#解决骑士遍历问题

问题

有一个5*5的棋盘，一个棋子从左上角开始，按照国际象棋的走法进行前进，如何不重复的走完所有格子，一共有多少种解法。

思路

首先需要知道国际象棋的马走日是怎么走法，这个请自行搜索
其次，如何记录棋盘的路径，我们决定采用二维数组
通过什么方法进行走，可以用递归的方法

编写

首先生成两个二维数组，定义一些基础变量

int count = 0;//统计数量
int solution = 0;//解决方案
static int n = 5;//常量
//二维数组8行2列 用于计算下一步坐标
int[,] move = new int[8, 2] { { -1, -2 }, { -2, -1 }, { -2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 } };
public int[,] board = new int[n, n];//棋盘

判断下一个点是否有效

bool IsOK(int x, int y)//判断下一个点是否有效
{
    if ((x <= n - 1) && (x >= 0)
        && (y <= n - 1) && (y >= 0)
        && (board[x, y] == 0))
    {
        return true;
    }
    else
    {
        return false;
    }
}

画出棋盘

        void Show()//画出棋盘
        {
            Console.WriteLine("第{0}种解", solution++);
            for (int i = 0; i < n; i++)//第i行
            {
                for (int j = 0; j < n; j++)//第j列
                {
                    Console.Write("  " + board[i, j]);
                }
                Console.WriteLine();
            }
            Console.WriteLine("-----");

        }

递归的方式进行遍历

        void DFS(int row, int col)
        {
            int nextX;
            int nextY;

            for (int i = 0; i < 8; i++)//因为是8个点，所以之前move数组是8行2列，此处要小于8
            {
                nextX = row + move[i, 0];//计算下一坐标行值
                nextY = col + move[i, 1];//计算下一坐标列值
                if (IsOK(nextX, nextY))//判断下一个点是否有效（未超出边界，且未走过）

                {
                    if (count < 24)//5*5的格子一共25格，除去起始点1个，还剩24个
                    {
                        count++;//步数+1
                        board[nextX, nextY] = count;//将下一个点的值改为非0，也就是当前步数
                        //递归计算下一个点，若下一点不满足，则回溯回本层，将下一点的值改回0，步数减1
                        DFS(nextX, nextY);
                        board[nextX, nextY] = 0;
                        count--;

                    }
                    else//步数=24步，已经走完所有格子，输出当前棋盘
                    {
                        Show();
                    }

                }
            }

main函数

        static void Main(string[] args)
        {
            Program p = new Program();

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    p.board[i, j] = 0;
                }
            }
            p.board[0, 0] = 1;//定义初始点
            p.count = 1;//定义初始步数
            p.DFS(0, 0);//递归开始
            Console.ReadKey();
        }
    }