Knight Tour problem

骑士之旅问题是著名的棋盘上骑士问题之一。骑士应该每到一个广场都要去一次。

接下来我们有两个案例：

封闭式巡更：骑士在距离起始方格一步的方格上结束。这意味着，如果它继续以迄今为止一直遵循的相同路径移动，它将能够再次遍历所有方块。

公开巡演：骑士在任何其他广场结束。

这个问题在n x n棋盘上解决了。

“n”可以有任何值。

这个问题源于图论中的哈密顿路径问题。

哈密顿路径问题的重点是找出从起点到终点的无向图中是否存在路径或路由。然而，即使它的大小几乎没有增加，它也会变得非常复杂。

哈密顿路径是只访问图的每个顶点一次的路径。具有哈密顿路径的图称为可追踪图。

然而，有一些方法可以在线性时间内解决这个问题。

考虑下图，让钻石代表“骑士”，记号代表其在给定位置的可能移动。“骑士”可以在基数方向移动两个方块，然后在正交方向移动一个方块。

回溯（backtracking）算法

回溯是一种算法范式，它尝试不同的解决方案，直到找到一个“有效”的解决方案。通常使用回溯技术解决的问题具有以下共同特性。这些问题只能通过尝试每种可能的配置来解决，并且每种配置只尝试一次。这些问题的一个简单解决方案是尝试所有配置，并输出符合给定问题约束的配置。回溯以增量方式工作，是对原始解决方案的优化，在该解决方案中生成并尝试所有可能的配置。

例如，考虑以下骑士之旅问题。

问题陈述：

给出一个N*N的棋盘，骑士被放置在空棋盘的第一块上。按照国际象棋规则移动的骑士必须精确地访问每个方块一次。打印每个单元格的访问顺序。

介绍

这篇文章是回溯系列的延续。你可以在这里参考其他类似的帖子。在这篇文章中，我们将讨论骑士之旅的问题。问题是，给定一个N*M棋盘，骑士之旅被定义为骑士的一系列动作，这样骑士只会访问每一个方格一次。

这听起来相似吗？

是的，这类似于找到本文中定义的哈密顿路径。

骑士巡演问题的求解方法

这里我定义了回溯方法来解决这个问题。让骑士从任何位置开始（在不丧失一般性的情况下，我们可以假设起点为0,0）

对于放置在棋盘任何单元格上的骑士，最多可以有八个有效移动，可以通过相对位置（{2，1}，{2，-1}，{1，2}，{1，-2}，{2，1}，{-2，-1}，

{ -1, 2 }, { -1, -2 } }

定义安全移动

那么让我们来定义一下，对于骑士来说，哪个牢房是安全的。主要有三个条件：

目标单元格必须在电路板的边界内

不能已经访问它

它必须可以从当前单元格位置y进行上述任何移动。

定义战略

假设骑士在一个位置（r，c），他已经覆盖了k-1细胞，我们必须为第k步选择细胞。然后，想法是尝试所有可能的安全动作，找到安全动作后，只需将骑士放在新识别的单元格中，然后尝试第（k+1）步。

但是等等！如果在这条线下的某个地方，我们发现没有安全的移动，并且仍有细胞存在，那该怎么办。

在这种情况下，我们拒绝部分解决方案，并清空发生此故障后的前一个单元格。

我们继续再次尝试单元格的其余移动。

我们重复这个过程，直到我们能够按照指南覆盖所有单元格。

源代码：POWER BY 315SOFT.COM

 

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
 
namespace Legalsoft.Truffer.Algorithm
{
	public static partial class Algorithm_Gallery
	{
		private static bool KTP_IsSafe(int N, int x, int y, int[,] sol)
		{
			return (x >= 0 && x < N && y >= 0 && y < N && sol[x, y] == -1);
		}
 
        public static bool KTP_Solve(out int[,] result)
		{
			int N = 8;
			result = new int[N, N];
			for (int x = 0; x < N; x++)
			{
				for (int y = 0; y < N; y++)
				{
					result[x, y] = -1;
				}
			}
			int[] xMove = { 2, 1, -1, -2, -2, -1, 1, 2 };
			int[] yMove = { 1, 2, 2, 1, -1, -2, -2, -1 };
 
			result[0, 0] = 0;
 
			if (KTP_Solve_Utility(N, 0, 0, 1,ref result, xMove, yMove) == false)
			{
				return false;
			}
			else
			{
				//printSolution(sol);
			}
			return true;
		}
 
		private static bool KTP_Solve_Utility(int N, int x, int y, int movei,ref int[,] result, int[] xMove, int[] yMove)
		{
			if (movei == N * N)
			{
				return true;
			}
			for (int k = 0; k < 8; k++)
			{
				int next_x = x + xMove[k];
				int next_y = y + yMove[k];
				if (KTP_IsSafe(N, next_x, next_y, result))
				{
					result[next_x, next_y] = movei;
					if (KTP_Solve_Utility(N, next_x, next_y, movei + 1,ref result, xMove, yMove))
					{
						return true;
					}
					else
					{
						result[next_x, next_y] = -1;
					}
				}
			}
 
			return false;
		}
 
	}
}