Cách tìm số bước tối thiểu cho mã quân Knight đến đích bằng C#

Chúng ta cần khiến mã Knight đi qua tất cả các ô của bàn cờ và mỗi ô chỉ được đến một lần.

Có hai cách kết thúc di chuyển của Knight: thứ nhất là Knight cách ô bắt đầu một nước đi, có thể quay về vị trí khởi tạo tạo thành vòng lặp (closed tour); thứ hai là Knight dừng ở bất kỳ vị trí nào khác (open tour). Một nước đi hợp lệ nếu nó nằm trong bàn cờ và ô đó chưa được chiếm. Chúng ta sẽ đặt giá trị của tất cả các ô chưa chiếm bằng -1.

Ví dụ

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace ConsoleApplication
{
    public class KnightWalkProblem
    {
        public class Cell
        {
            public int x, y;
            public int dis;
            public Cell(int x, int y, int dis)
            {
                this.x = x;
                this.y = y;
                this.dis = dis;
            }
        }

        static bool IsInside(int x, int y, int N)
        {
            if (x >= 1 && x <= N && y >= 1 && y <= N)
                return true;
            return false;
        }

        public int MinStepToReachTarget(int[] knightPos, int[] targetPos, int N)
        {
            int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
            int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };
            Queue<Cell> q = new Queue<Cell>();
            q.Enqueue(new Cell(knightPos[0], knightPos[1], 0));
            Cell t;
            int x, y;
            bool[,] visit = new bool[N + 1, N + 1];
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++)
                    visit[i, j] = false;
            visit[knightPos[0], knightPos[1]] = true;
            while (q.Count != 0)
            {
                t = q.Peek();
                q.Dequeue();
                if (t.x == targetPos[0] && t.y == targetPos[1])
                    return t.dis;
                for (int i = 0; i < 8; i++)
                {
                    x = t.x + dx[i];
                    y = t.y + dy[i];
                    if (IsInside(x, y, N) && !visit[x, y])
                    {
                        visit[x, y] = true;
                        q.Enqueue(new Cell(x, y, t.dis + 1));
                    }
                }
            }
            return int.MaxValue;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            KnightWalkProblem kn = new KnightWalkProblem();
            int N = 30;
            int[] knightPos = { 1, 1 };
            int[] targetPos = { 30, 30 };
            Console.WriteLine(kn.MinStepToReachTarget(knightPos, targetPos, N));
        }
    }
}

Kết quả

20

Giải thích: Sử dụng thuật toán BFS (Breadth-First Search) để tìm đường đi ngắn nhất. Knight di chuyển theo 8 hướng có thể. Trên bàn cờ 30x30, từ (1,1) đến (30,30) cần tối thiểu 20 nước đi.