skknightplus.cs

有本书所有程序的源代码,包括聊天系统,马的遍历等问题

/*
 * 骑士结构定义
 * 
 * 类型		长度	数量	说明
 * int		1		1		棋盘标志数组内存地址
 * int		1		1		下一步索引	
 * int		2		8		下一步出口数以及棋盘标志数组内存地址
 * 
 * 总计:	int[18]
 * 
 */

/*
 * 调试定义
 * 
 * PRINTSTEP	输出当前遍历步骤
 * PRINTALL		输出当前遍历步骤(骑士遍历路线)
 * PRINTTOUR	输出当前遍历步骤(骑士巡游路线)
 * 
 */

/*
 *	棋盘定义
 * 
 *	   ──────────→ y		   ──────────→ y
 *	│ ××××××××××××		│ ××××××××××××
 *	│ ××××××××××××		│ ××××××××××××
 *	│ ××□■□■□×××××		│ ××□04□03□×××××
 *	│ ××■□□□■×××××		│ ××05□□□02×××××
 *	│ ××□□●□□×××××		│ ××□□●□□×××××
 *	│ ××■□□□■×××××		│ ××06□□□01×××××
 *	│ ××□■□■□×××××		│ ××□07□00□×××××
 *	│ ××××××××××××		│ ××××××××××××
 *	│ ××××××××××××		│ ××××××××××××
 *	│ ××××××××××××		│ ××××××××××××
 *	↓ ××××××××××××		↓ ××××××××××××
 *	x  ××××××××××××		x  ××××××××××××
 * 
 * Line Stride = 12
 * 
 * index	offset
 * 00		25
 * 01		-11
 * 02		-24
 * 03		-13
 * 04		-2
 * 05		11
 * 06		24
 * 07		13
 * 
 */

using System;

namespace KnightTourPlus
{
	class SKKnightPlus
	{
		#region 私有常量

		/// <summary>
		/// 骑士起始点X坐标
		/// </summary>
		private readonly int m_StartX;

		/// <summary>
		/// 骑士起始点Y坐标
		/// </summary>
		private readonly int m_StartY;

		/// <summary>
		/// 地址偏移量数组
		/// </summary>
		private readonly int[] m_Delta = { 25, -11, -24, -13, -2, 11, 24, 13 };

		#endregion 私有常量

		#region 私有变量

		/// <summary>
		/// 骑士遍历次数
		/// </summary>
		private ulong m_ResultCount;

		/// <summary>
		/// 骑士巡游次数
		/// </summary>
		private ulong m_HamiltonCount;

		/// <summary>
		/// 搜索开始时间
		/// </summary>
		private long m_StartTicks;

		/// <summary>
		/// 搜索结束时间
		/// </summary>
		private long m_EndTicks;

		#endregion 私有变量

		#region 私有方法

		/// <summary>
		/// 初始化
		/// </summary>
		/// <param name="pCheckFlag">棋盘标志指针</param>
		private unsafe void Init( int* pCheckFlag )
		{
			for ( int i = 0; i < 12; i++ )
			{
				for ( int j = 0; j < 12; j++ )
				{
					if ( i == 0 || i == 1 || i == 10 || i == 11 || j == 0 || j == 1 || j == 10 || j == 11 )
						*pCheckFlag = -1;
					else
						*pCheckFlag = 0;
					pCheckFlag++;
				}
			}

			this.m_ResultCount = 0;
			this.m_HamiltonCount = 0;
		}

		/// <summary>
		/// 输出结果
		/// 累加巡游数量
		/// </summary>
		private void OutputResult()
		{
			this.m_HamiltonCount += 2;
			if ( this.m_HamiltonCount % 1000 == 0 )
			{
				this.m_EndTicks = DateTime.Now.Ticks;
				Console.WriteLine( "Hamilton: {0} on the {1} Result. Elapse {2} milliseconds", this.m_HamiltonCount, this.m_ResultCount, ( this.m_EndTicks - this.m_StartTicks ) / 10000 );
			}
		}

		/// <summary>
		/// 判断是否为巡游路线
		/// </summary>
		/// <param name="pFinish">结束点数组指针</param>
		/// <param name="FinishAdd">结束点地址</param>
		/// <returns>是否为巡游结束结点</returns>
		private unsafe bool CheckTour( int* pFinish, int FinishAddress )
		{
			int i = *pFinish;
			pFinish++;
			for ( ; i < 8 && *pFinish != 0; i++, pFinish++ )
			{
				if ( *pFinish == FinishAddress )
				{
					return true;
				}
			}

			return false;
		}

		private unsafe void CheckHadSearch( int* pFinish, int RemoveAddress )
		{
			if ( pFinish[ pFinish[ 0 ] ] == RemoveAddress )
				( *pFinish )++;
		}

		/// <summary>
		/// 获取结束点地址数组
		/// </summary>
		/// <param name="pFinish">结束点数组指针</param>
		/// <param name="pCFStartKnight">起始骑士棋盘标志指针</param>
		private unsafe void GetFinishAdd( int* pFinish, int* pCFStartKnight )
		{
			*pFinish = 1;
			pFinish++;
			int i = 0;
			for ( ; i < 8; i++ )
			{
				pCFStartKnight += this.m_Delta[ i ];
				if ( *pCFStartKnight == 0 )
				{
					*pFinish = ( int )pCFStartKnight;
					pFinish++;
				}
			}
			if ( i < 8 )
				*pFinish = 0;
		}

		/// <summary>
		/// 获取骑士可走的所有下一步
		/// 并按下一步出口数量升序排列
		/// </summary>
		/// <param name="pKnight">指向当前骑士指针</param>
		private unsafe void Navigator( int* pKnight )
		{
			int* pCFNextKnight = ( int* )pKnight[ 0 ];
			int* pCFTempKnight;

			pKnight += 2;

			int count = 0;

			for ( int i = 0; i < 8; i++ )
			{
				pCFNextKnight += this.m_Delta[ i ];

				pKnight[ 0 ] = 0;						// sorce
				pKnight[ 1 ] = ( int )pCFNextKnight;	// address of checkflag

				if ( *pCFNextKnight == 0 )
				{
					pCFTempKnight = pCFNextKnight;
					for ( int j = 0; j < 8; j++ )
					{
						pCFTempKnight += this.m_Delta[ j ];
						if ( *pCFTempKnight == 0 )
							( *pKnight )++;
					}
					count++;
				}
				else
				{
					*pKnight = 8888;
				}
				pKnight += 2;
			}

			if ( count < 1 )
				return;

			pKnight -= 16;

			// sort
			int tmp;
			int* pMinSorce;
			int* pTemp;
			for ( int i = 0; i < count; i++, pKnight += 2 )
			{
				pMinSorce = pKnight;
				pTemp = pMinSorce + 2;

				for ( int j = i + 1; j < 8; j++ )
				{
					if ( *pTemp < *pMinSorce )
					{
						pMinSorce = pTemp;
					}
					pTemp += 2;
				}
				if ( pMinSorce == pKnight )
					continue;

				tmp = pKnight[ 0 ];
				pKnight[ 0 ] = pMinSorce[ 0 ];
				pMinSorce[ 0 ] = tmp;

				tmp = pKnight[ 1 ];
				pKnight[ 1 ] = pMinSorce[ 1 ];
				pMinSorce[ 1 ] = tmp;

			}
		}

		/// <summary>
		/// 从起始骑士位置开始搜索
		/// </summary>
		/// <param name="pKnight">指向起始骑士指针</param>
		/// <param name="pFinish">结束点数组指针</param>
		/// <param name="pCFRoot">棋盘标志数组起始指针</param>
		/// <remarks>棋盘标志数组起始指针用于输出结果验证</remarks>
		private unsafe void NoRecursionSearch( int* pKnight, int* pFinish, int* pCFRoot )
		{
			int step = 0;
			int* pCFNextKnight;
			while ( step >= 0 )
			{
				if ( pKnight[ 1 ] == 8 || pKnight[ 2 + pKnight[ 1 ] * 2 ] == 8888 )
				{
					*( int* )pKnight[ 0 ] = 0;
					this.CheckHadSearch( pFinish, *pKnight );
					pKnight -= 18;
					--step;
					continue;
				}

				pCFNextKnight = ( int* )pKnight[ 3 + pKnight[ 1 ] * 2 ];
				pKnight[ 1 ]++;

				*pCFNextKnight = ++step + 1;

#if PRINTSTEP
				// 打印当前遍历路线,用于调试
				PrintResult( pCFRoot );
#endif

				pKnight += 18;

				pKnight[ 0 ] = ( int )pCFNextKnight;
				pKnight[ 1 ] = 0;

				this.Navigator( pKnight );

				if ( step == 63 )
				{
#if PRINTALL
					// 打印当前遍历路线,用于调试(遍历棋盘路线)
					PrintResult( pCFRoot );
#endif
					m_ResultCount++;
					if ( CheckTour( pFinish, *pKnight ) )
					{
#if PRINTTOUR
						// 打印当前遍历路线,用于调试(巡游路线)
						PrintResult( pCFRoot );
#endif

						OutputResult();
					}
				}
			}
			this.m_EndTicks = DateTime.Now.Ticks;
			Console.WriteLine( "Search Finished. Total {0} on the {1} Result. Elapse {2} milliseconds", this.m_HamiltonCount, this.m_ResultCount, ( this.m_EndTicks - this.m_StartTicks ) / 10000 );
		}

		/// <summary>
		/// 打印当前遍历路线
		/// </summary>
		/// <param name="pCFRoot">棋盘标志数组起始指针</param>
		/// <remarks>此输出仅仅用于验证遍历路线是否正确,当测试性能时请关闭此输出</remarks>
		private unsafe void PrintResult( int* pCFRoot )
		{
			pCFRoot += 26;
			for ( int i = 0; i < 8; i++ )
			{
				for ( int j = 0; j < 8; j++ )
				{
					Console.Write( "{0:00} ", *pCFRoot );
					pCFRoot++;
				}
				pCFRoot += 4;
				Console.WriteLine();
			}
			Console.ReadLine();
		}

		#endregion 私有方法

		#region 公共方法

		/// <summary>
		/// 开始搜索
		/// </summary>
		public unsafe void StartSearch()
		{
			/// <summary>
			/// 棋盘标志数组
			/// </summary>
			/// <remarks>
			/// -1:	边界冗余
			/// 0:	没有走过
			/// >0:	巡游步数
			/// </remarks>
			int* pCheckFlag = stackalloc int[ 144 ];

			/// <summary>
			/// 骑士数组
			/// </summary>
			int* pKnights = stackalloc int[ 1152 ];

			/// <summary>
			/// 结束点数组
			/// </summary>
			int* pFinish = stackalloc int[ 9 ];

			/// <summary>
			/// 棋盘标志数组起始指针
			/// </summary>
			int* pCFRoot = pCheckFlag;

			/// <summary>
			/// 起始骑士棋盘标志地址指针
			/// </summary>
			int* pCFStartKnight = pCheckFlag + this.m_StartX + this.m_StartY * 12;

			this.Init( pCheckFlag );

			this.GetFinishAdd( pFinish, pCFStartKnight );

			this.m_StartTicks = DateTime.Now.Ticks;

			pKnights[ 0 ] = ( int )pCFStartKnight;
			pKnights[ 1 ] = 0;
			*pCFStartKnight = 1;
			this.Navigator( pKnights );

			this.NoRecursionSearch( pKnights, pFinish, pCFRoot );

		}

		#endregion 公共方法

		#region 构造函数

		/// <summary>
		/// 骑士巡游类构造函数
		/// </summary>
		/// <param name="startx">开始点X坐标</param>
		/// <param name="starty">开始点y坐标</param>
		public SKKnightPlus( int startx, int starty )
		{
			this.m_StartX = startx + 2;
			this.m_StartY = starty + 2;
		}

		#endregion 构造函数

	}
}