queen.java

已经编写好的数据结构课本程序可以减轻您的负担

// =============== Program Description =============== 
// 程序名称： queen.java
// 程序目的： 运用递归来解N皇后问题                 
// Written By Kuo-Yu Huang. (WANT Studio.)            
// ===================================================
import ConsoleReader.*;					// 导入已定义的数据输入类

public class queen
{
							// 声明8*8的空白棋盘	
	public static char Chessboard[][] = new char[8][8];
	public static void main (String args[])
	{
		int	i,j;			// 循环计数变量	

		for (i=0;i<8;i++)
			for (j=0;j<8;j++)
				Chessboard[i][j] = 'X';
		N_Queens(0,0,0);
	
		System.out.println("The graph of 8 Queens on the Cheesboard.");
		System.out.println("      0   1   2   3   4   5   6   7  ");
		System.out.println("    +---+---+---+---+---+---+---+---+");

		for (i=0;i<8;i++)
		{
			System.out.print(" "+i+" |");
			for (j=0;j<8;j++)
				System.out.print("-"+Chessboard[i][j]+"-|");
			System.out.println("");				
			System.out.println("    +---+---+---+---+---+---+---+---+");
		}
	}
	
// --------------------------------------------------- 
// 递归解N皇后问题                                     
// --------------------------------------------------- 
	public static int N_Queens(int LocX,int LocY,int Queens)
	{
		int	i,j;			// 循环计数变量	
		int	Result = 0;

		if ( Queens == 8 )		// 递归结束条件 
			return 1;
		else				// 递归执行部分 
			if ( QueenPlace(LocX,LocY) )
			{
				Chessboard[LocX][LocY] = 'Q';
				for (i=0;i<8;i++)
					for (j=0;j<8;j++)
					{
						Result += N_Queens(i,j,Queens+1);
						if (Result > 0)
							break;
					}
				if (Result > 0)
					return 1;
				else
				{
					Chessboard[LocX][LocY] = 'X';
					return 0;
				}
			}
			else
				return 0;
	}

// --------------------------------------------------- 
// 判断传入座标是否可放置皇后                          
// --------------------------------------------------- 
	public static boolean QueenPlace(int LocX,int LocY)
	{
		int	i,j;

		if (Chessboard[LocX][LocY] != 'X')	// 判断是否有皇后	
			return false;

		for (j=LocY-1;j>=0;j--)			// 判断上方是否有皇后	
			if (Chessboard[LocX][j] != 'X')
				return false;

		for (j=LocY+1;j<8;j++)			// 判断下方是否有皇后	
			if (Chessboard[LocX][j] != 'X')
				return false;

		for (i=LocX-1;i>=0;i--)			// 判断左方是否有皇后	
			if (Chessboard[i][LocY] != 'X')
				return false;

		for (i=LocX+1;i<8;i++)			// 判断右方是否有皇后	
			if (Chessboard[i][LocY] != 'X')
				return false;

		i = LocX - 1;
		j = LocY - 1;
		while ( i>=0 && j>=0 )			// 判断左上方是否有皇后	
			if (Chessboard[i--][j--] != 'X')
				return false;
	
		i = LocX + 1;
		j = LocY - 1;
		while ( i<8 && j>=0 )			// 判断右上方是否有皇后	
			if (Chessboard[i++][j--] != 'X')
				return false;
	
		i = LocX - 1;
		j = LocY + 1;
		while ( i>=0 && j<8 )			// 判断左下方是否有皇后	
			if (Chessboard[i--][j++] != 'X')
				return false;
	
		i = LocX + 1;
		j = LocY + 1;
		while ( i<8 && j<8 )			// 判断右下方是否有皇后	
			if (Chessboard[i++][j++] != 'X')
				return false;
		return true;
	}
}