问题描述

将马随机放在国际象棋的8×8棋盘的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。

运用的算法

• 递归
• 回溯
• 贪心（可选）

  代码

  还可以优化，用贪心算法，每次递归进入当前马能走的最少的点。这样回溯就少了很多步骤

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Globalization;
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
namespace ConsoleApp1
{
    class Program
    {
        public static int X;//棋盘x长度
        public static int Y;//棋盘y长度
        //创建一个数组，标记棋盘的各个位置是否被访问过了
        public static bool[] visited;
        //使用一个变量标记是否棋盘的所有位置都被访问
        public static bool finished;//如果为true，表示成功
        static void Main(string[] args)
        {
            X = 6;
            Y = 6;
            int row = 2;//初始位置从1开始
            int col = 4;
            //棋盘
            int[,] chessboard=new int[X,Y];
            visited = new bool[X * Y];
            DateTime st = DateTime.Now;
            traversalChessborad(chessboard, row - 1, col - 1, 1);
            DateTime et = DateTime.Now;
            Console.WriteLine($"计算用时：{(et-st).TotalMilliseconds}毫秒");
            //输出棋盘
            for(int i = 0; i < chessboard.GetLength(0); i++)
            {
                for(int j=0;j< chessboard.GetLength(1); j++)
                    Console.Write(chessboard[i,j]+"  ");
                Console.WriteLine();
            }
        }
        //完成骑士周游问题算法
        //chessboard棋盘
        //row 当前位置的行从0开始
        //col 当前位置的列从0开始
        //step 是第几步，初始位置就是第一步
        public static void traversalChessborad(int[,] chessboard,int row,int col,int step)
        {
            chessboard[row,col] = step;
            //标记为已访问,从棋盘上数第几个位置
            visited[row * X + col] = true;
            //获取当前位置可以走的下一个位置的集合
            List<Point> ps = next(new Point(col, row));
            //遍历
            while (ps.Count != 0)
            {
                //取出下一个可以走的位置
                Point p = ps[0];
                ps.Remove(p);
                //判断该点是否已经访问过了
                if (!visited[p.Y * X + p.X])//说明没有访问过
                {
                    traversalChessborad(chessboard, p.Y, p.X, step+1);//一定要step+1，（用step++或者++step把step自身都加了1，下次回溯到这里时，步骤已经+1了）
                }
            }
            //判断是否完成任务，step和应该走的步数比较，如果没有达到数量，则表示没有完成任务
            if (step < X * Y && !finished)
            {
                chessboard[row, col] = 0;
                visited[row * X + col] = false;
            }
            else
            {
                finished = true;
            }
        }
        //根据当前的位置，计算马儿还能走哪些位置，放入list中，最多有8个位置
        public static List<Point> next(Point cp)
        {
            List <Point> list = new List<Point>();
            int x = 0,y = 0;
            //马走日的规则，>=0表示没有索引越界。
            if ((x = cp.X - 2) >= 0 && (y = cp.Y - 1) >= 0) //左2上1
                list.Add(new Point(x, y));
            if ((x = cp.X - 1) >= 0 && (y = cp.Y - 2) >= 0)//左1上2
                list.Add(new Point(x, y));
            if ((x = cp.X + 1) < X && (y = cp.Y - 2) >= 0)//右1上2
                list.Add(new Point(x, y));
            if ((x = cp.X + 2) < X && (y = cp.Y - 1) >= 0)//右2上1
                list.Add(new Point(x, y));
            if ((x = cp.X + 2) < X && (y = cp.Y + 1) < Y)//右2下1
                list.Add(new Point(x, y));
            if ((x = cp.X + 1) < X && (y = cp.Y + 2) < Y)//右1下2
                list.Add(new Point(x, y));
            if ((x = cp.X - 1) >= 0 && (y = cp.Y + 2) < Y)//左1下2
                list.Add(new Point(x, y));
            if ((x = cp.X - 2) >= 0 && (y = cp.Y + 1) < Y)//左2下1
                list.Add(new Point(x, y));
            return list;
        }
    }
}