C# 实现马踏棋盘

2020/01/08 112

算法 递归

在国际象棋盘中,将🐴放置任意位置,在🐴不走重复路的情况下,如何踏遍每个格子?

马踏棋盘

class Program
{
    // 对于 n * n 的棋盘上,当 n >= 5 且为偶数时,任意点作为起点都有解。
    const int SIZE_X = 6;
    const int SIZE_Y = 6;
    static int[,] _chessboard;

    static void Main(string[] args)
    {
        _chessboard = new int[SIZE_X, SIZE_Y];

        TraveChessBoard(0, 0, 1);

        for (int i = 0; i < SIZE_X; i++)
        {
            for (int j = 0; j < SIZE_Y; j++)
            {
                Console.Write(_chessboard[i, j]);
                if ((j + 1) % SIZE_Y != 0)
                {
                    Console.Write('\t');
                }
            }
            Console.Write('\n');
        }
    }

    // 找到基于 (x,y) 位置的下一个可走的位置
    static bool CheckNext(int tryCount, ref int x, ref int y)
    {
        switch (tryCount)
        {
            case 1:
                {
                    int newX = x - 1;
                    int newY = y + 2;
                    if (newX >= 0 && newY <= SIZE_Y - 1 && _chessboard[newX, newY] == 0)
                    {
                        x = newX;
                        y = newY;
                        return true;
                    }
                }
                break;
            case 2:
                {
                    int newX = x + 1;
                    int newY = y + 2;
                    if (newX <= SIZE_X - 1 && newY <= SIZE_Y - 1 && _chessboard[newX, newY] == 0)
                    {
                        x = newX;
                        y = newY;
                        return true;
                    }
                }
                break;
            case 3:
                {
                    int newX = x + 2;
                    int newY = y + 1;
                    if (newX <= SIZE_X - 1 && newY <= SIZE_Y - 1 && _chessboard[newX, newY] == 0)
                    {
                        x = newX;
                        y = newY;
                        return true;
                    }
                }
                break;
            case 4:
                {
                    int newX = x + 2;
                    int newY = y - 1;
                    if (newX <= SIZE_X - 1 && newY >= 0 && _chessboard[newX, newY] == 0)
                    {
                        x = newX;
                        y = newY;
                        return true;
                    }
                }
                break;
            case 5:
                {
                    int newX = x + 1;
                    int newY = y - 2;
                    if (newX <= SIZE_X - 1 && newY >= 0 && _chessboard[newX, newY] == 0)
                    {
                        x = newX;
                        y = newY;
                        return true;
                    }
                }
                break;
            case 6:
                {
                    int newX = x - 1;
                    int newY = y - 2;
                    if (newX >= 0 && newY >= 0 && _chessboard[newX, newY] == 0)
                    {
                        x = newX;
                        y = newY;
                        return true;
                    }
                }
                break;
            case 7:
                {
                    int newX = x - 2;
                    int newY = y - 1;
                    if (newX >= 0 && newY >= 0 && _chessboard[newX, newY] == 0)
                    {
                        x = newX;
                        y = newY;
                        return true;
                    }
                }
                break;
            case 8:
                {
                    int newX = x - 2;
                    int newY = y + 1;
                    if (newX >= 0 && newY <= SIZE_Y - 1 && _chessboard[newX, newY] == 0)
                    {
                        x = newX;
                        y = newY;
                        return true;
                    }
                }
                break;
            default:
                throw new NotImplementedException();
        }
        return false;
    }

    // 深度优先遍历棋盘
    // (x,y) 为位置坐标
    // tag 是标记变量,每走一步 tag+1
    static bool TraveChessBoard(int x, int y, int tag)
    {
        int count = 1, x1 = x, y1 = y;
        _chessboard[x, y] = tag;
        if (tag == SIZE_X * SIZE_Y)
        {
            return true;
        }

        bool flag = CheckNext(count, ref x1, ref y1);
        while (!flag && count < 8)
        {
            count++;
            flag = CheckNext(count, ref x1, ref y1);
        }

        while (flag)
        {
            if (TraveChessBoard(x1, y1, tag + 1))
            {
                return true;
            }
            x1 = x;
            y1 = y;
            if (count < 8)
            {
                count++;
                flag = CheckNext(count, ref x1, ref y1);
            }
            else
            {
                flag = false;
            }
            while (!flag && count < 8)
            {
                count++;
                flag = CheckNext(count, ref x1, ref y1);
            }
        }
        if (!flag)
        {
            _chessboard[x, y] = 0;
        }
        return false;
    }
}
评论