重新整理数据结构与算法(c#)——算法套马踏棋算法[三十三]

前言

马踏棋盘 概念在这，不做过多复述。

https://baike.sogou.com/v58959803.htm?fromTitle=马踏棋盘

思路是这样子的，一匹马有上面几种做法，然后进行尝试，然后回溯即可。

我的测试结果是没有用贪心用了 10分钟，用贪心 20秒不到。

正文

class Program
{
	//棋盘列数
	public static int X;
	//棋盘行数
	public static int Y;
	//标志棋盘的各个位置是否被访问
	private static bool[] visited;
	//是否访问成功
	private static bool finished;

	public static Point Override { get; private set; }

	static void Main(string[] args)
	{
		X = 8;
		Y = 8;
		int row = 1; //马儿初始位置的行，从1开始编号
		int column = 1; //马儿初始位置的列，从1开始编号
						//创建棋盘
		int[,] chessboard = new int[X, Y];
		visited = new bool[X * Y];//初始值都是false
		Stopwatch stopwatch = new Stopwatch();
		stopwatch.Start();
		traversalChessboard(chessboard, row - 1, column - 1, 1);
		stopwatch.Stop();
		for (int i = 0; i < X - 1; i++)
		{
			for (int j = 0; j < Y - 1; j++)
			{
				Console.Write(chessboard[i, j] + "  ");
			}
			Console.WriteLine();
		}
		Console.Read();
	}

	public static void traversalChessboard(int[,] chessboard, int row, int column, int step)
	{
		//Thread.Sleep(500);
		//第几步
		chessboard[row, column] = step;
		Console.WriteLine("走x轴"+row+"y轴:"+column);
		//表示这个点被访问了
		visited[row * X + column] = true;
		List<Point> ps = next(new Point(column, row));
		sort(ps);
		while (ps.Count != 0)
		{
			Point p = ps[0];
			ps.Remove(p);
			if (!visited[p.Y * X + p.X])
			{
				traversalChessboard(chessboard, p.Y, p.X, step + 1);
			}
		}
		if (step < X * Y && !finished)
		{
			Console.WriteLine("重置x轴" + row + "y轴:" + column);
			//如果没有完成回溯重置
			chessboard[row,column] = 0;
			visited[row * X + column] = false;
		}
		else
		{
			finished = true;
		}
	}
	public class Point {

		public Point(int x,int y)
		{
			this.X = x;
			this.Y = y;
		}
		public Point()
		{

		}
		public int X
		{
			set;
			get;
		}
		public int Y
		{
			set;
			get;
		}
	}

	public static List<Point> next(Point curPoint)
	{
		List<Point> points = new List<Point>();
	  
		Point point6 = new Point();
		//显示5位置
		if ((point6.X = curPoint.X - 2) >= 0 && (point6.Y = curPoint.Y - 1) >= 0)
		{
			points.Add(point6);
		}
		Point point7 = new Point();
		//显示6位置
		if ((point7.X = curPoint.X - 1) >= 0 && (point7.Y = curPoint.Y - 2) >= 0)
		{
			points.Add(point7);
		}
		Point point8 = new Point();
		//显示7位置
		if ((point8.X = curPoint.X + 1) < X && (point8.Y = curPoint.Y - 2) >= 0)
		{
			points.Add(point8);
		}
		Point point1 = new Point();
		//显示0位置
		if ((point1.X = curPoint.X + 2) <X && (point1.Y = curPoint.Y - 1) >= 0)
		{
			points.Add(point1);
		}
		Point point2 = new Point();
		//显示1位置
		if ((point2.X = curPoint.X + 2) <X && (point2.Y = curPoint.Y + 1) < Y)
		{
			points.Add(point2);
		}
		Point point3 = new Point();
		//显示2位置
		if ((point3.X = curPoint.X + 1) <X && (point3.Y = curPoint.Y + 2) <Y)
		{
			points.Add(point3);
		}
		Point point4 = new Point();
		//显示3位置
		if ((point4.X = curPoint.X - 1) >= 0 && (point4.Y = curPoint.Y + 2) < Y)
		{
			points.Add(point4);
		}
		Point point5 = new Point();
		//显示4位置
		if ((point5.X = curPoint.X - 2) >= 0 && (point5.Y = curPoint.Y + 1) < Y)
		{
			points.Add(point5);
		}
	  
		return points;
	}
	//根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
	public static void sort(List<Point> ps)
	{
		ps.Sort(new companer());
	}

	public class companer : IComparer<Point>
	{
		public int Compare(Point x, Point y)
		{
			int count1 = next(x).Count;
			//获取到o2的下一步的所有位置个数
			int count2 = next(y).Count;
			if (count1 < count2)
			{
				return -1;
			}
			else if (count1 == count2)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
	}
}