class1.cs

回溯算法程序

using System;
using System.Collections;
using System.Text;

namespace HuiSuBaHuangHou
{
	/// <summary>
	/// Class1 的摘要说明。
	/// </summary>
	class Class1
	{
		const int SIZE = 8;
		static int[] Queen = new int[SIZE]; //每个皇后的位置
		static int sum = 0; //皇后问题的方案数量
		static void Main(string[] args)
		{
			//初始位置应为未放置-8
			for (int i = 0; i < Queen.Length; i++)
			{
				Queen[i] = -8;
			}
 
			Trial(0);           
            
		}
 
        
 
		//使用回溯法放置棋子
		static void Trial(int n)
		{            
			for (int j = 0; j < SIZE; j++)
			{
				if (!IsConflict(n, j))
				{
					Queen[n] = j;
					if (n < SIZE - 1)
					{
						Trial(n + 1);
					}
					else
					{
						Console.WriteLine("第" + (++sum) + "种方案");
						Write();                   
					}
					Queen[n] = -8;
				}
                
			}            
            
		}
 
		//检测新皇后是否和已有的皇后互相冲突
		static bool IsConflict(int row, int place)
		{
			for (int i = 0; i < SIZE; i++)
			{
				if (Queen[i] == -8)
				{
					break;
				}
				//检查新皇后是否与以前的皇后能相互攻击
				if (place == Queen[i] || place == Queen[i] + row - i || place == Queen[i] - row + i)
				{                    
					return true;
				}
 
			}
			return false;
		}
 
 
		static void Write()
		{
			for (int i = 0; i < SIZE; i++)
			{
				for (int j = 0; j < SIZE; j++)
				{
					if (Queen[i] == j)
					{
						Console.Write("★");
					}
					else if ((i % 2 == 0 && j % 2 == 0) || i % 2 != 0 && j % 2 != 0)
					{
						Console.Write("□");
					}
					else
					{
						Console.Write("■");
					}
				}
				Console.WriteLine();
			}
 
			Console.WriteLine();
		}

	}
}