8_queen.cpp

8皇后问题。所谓著名的八皇后问题就是八个皇后在8*8的网格中排列时不能同在一行、一列或者一条斜线上。根据前人的研究

// 8_queen.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

//----------------------------------------------------------------------
//--------八皇后的非递归算法
//---------------------------------------------------------------------------------

void main() 
{ 
	int i;
	int A[8];//A[int i]标记每一行所放的皇后的未知 
	int flag;//标记 当flag=0没有冲突；flag=1有冲突
	int m=0;//总共有几种答案 
	int t,tt; 

	int n,z;

	for(int a=1;a<=8;a++) 
		for(int b=1;b<=8;b++) 
			for(int c=1;c<=8;c++) 
				for(int d=1;d<=8;d++) 
					for(int e=1;e<=8;e++) 
						for(int f=1;f<=8;f++) 
							for(int g=1;g<=8;g++) 
								for(int h=1;h<=8;h++) 
								{ 
									//构造棋盘外表
									char M[8][8];
									for(n=0;n<8;n++)
										for (z=0;z<8;z++)
											M[n][z]='-';

									A[0]=a; 
									A[1]=b; 
									A[2]=c; 
									A[3]=d; 
									A[4]=e; 
									A[5]=f; 
									A[6]=g; 
									A[7]=h; 
									//-------------------------比较是否在同一列 
									flag=0; 
									for(i=7;i>0;i--) 
									{ 
										for(int j=0;j<i;j++) 
										{
											if(A[i]==A[j]) 
											{ 
												flag=1; 
												break; 
											} 
										}
										if(flag) break; 
									} 

									if(!flag)
									{//---------------------------比较是否在对角线上 
										for(i=7;i>0;i--) 
										{ 
											for(int j=0;j<i;j++) 
											{ 
												t=A[i]; 
												tt=A[j]; 
												if(tt>t) 
												{ 
													tt=9-tt; 
													t=9-t; 
												} 
												if(t-i==tt-j) 
												{ 
													flag=1; 
													break; 
												} 
											} 
											if(flag) break; 
										}
									}
									if(!flag) 
									{ 
										/*for(i=0;i<=7;i++) 
											cout<<A[i]<<" "; 
										m++; 
										cout<<"************************"<<m<<endl; 
										getchar();*/
										for(i=0;i<=7;i++)
										{
											int cc=A[i];
											M[i][cc-1]='+';
										}
										m++;
										cout<<"No."<<m<<" method is:"<<endl;
										for(n=0;n<8;n++)
										{
											for(z=0;z<8;z++)
											{
												cout<<M[n][z]<<" ";
												if (z==7)
													cout<<endl;
											}
										}
										getchar();
									}
								} 
								getchar();
}