8皇后问题

 

描述：
八皇后问题是大数学家高斯于1850年提出来的。该问题是在8×8的国际象棋棋盘上放置8个皇后，使得没有一个皇后能“吃掉”任何其他一个皇后，即没有任何两个皇后被放置在棋盘的同一行、同一列或同一斜线上。

输出8皇后问题所有结果。

输入：

没有输入。

输出：

每个结果第一行是No n：的形式，n表示输出的是第几个结果；下面8行，每行8个字符，‘A’表示皇后，‘.’表示空格。不同的结果中，先输出第一个皇后位置靠前的结果；第一个皇后位置相同，先输出第二个皇后位置靠前的结果；依次类推。

输入样例：

输出样例：

输出的前几行：

No 1:

A.......

....A...

.......A

.....A..

..A.....

......A.

.A......

...A....

No 2:

A.......

.....A..

.......A

..A.....

......A.

...A....

.A......

....A...

答案：

#include<stdio.h>

#include<math.h>//要用到绝对值函数


 

inta[8];

intcounter=1;//计数器


 

voidsearch(int m); //递归函数


intcanplace(int row,int col);//判断是否满足八皇后的条件


voidoutput();

 

intmain()

{


  
search(0);//初始化为0


}


 

voidsearch(int m)

{

    
int i;

  
     if(m==8)

  
     {

  
         output();

  
     }

   
else

   
{

   
    for(i=0;i<8;i++)

          
{

               
if(canplace(m,i))

               
{

                    
a[m]=i;

                    
search(m+1);

               
}

          
}      

   
} 

}

 

intcanplace(int row,int col)

{

    
int i,flag=1; 

    
for(i=0;i<row;i++)

    
{

          
if(a[i]==col||fabs(row-i)==fabs(col-a[i]))

          
{

               
flag=0;

               
break;

          
} 

    
}

    
return(flag);

}

 

voidoutput ()

{

    
int i,j;

    
printf("No ");

    
printf("%d",counter);

    
printf(":\n");

    
counter++;

    
for(i=0;i<8;i++)

    
{

          
for(j=0;j<8;j++)

          
{

               
if(j==a[i])printf("A");

               
else printf("."); 

          
}

          
printf("\n");

    
}

    


}

注意：



本题用a[m]=j来表示皇后在第m行第j列，所以输出时一行只有一个皇后，故在canplace中无需再判断


输出时要二重循环才能输出矩阵


a[i]==col 
表示同一列的前n-1行中有皇后


fabs(row-i)==fabs(col-a[i])
表示在同一斜线上或在同一反斜线上

 

 

 

 

回溯法求解8皇后问题的优化
这是我第二次写博客了，第一次是五分钟前。马上就写完的时候浏览器突然崩溃了，还没有保存，心痛！

其实还是第一次写博客，这个优化的算法是我前几天写算法报告的作业，一直想写个博客试试，于是就把这个算法报告的内容搬上来了，本人是大二菜鸡一只，下面的内容可能会有很多的错误，如果您在阅读时发现了错误请告诉我，谢谢你的理解和阅读。

第一次写博客，可能写的比较恶心请大家见谅。如果内容雷同，那就是想到一起去了，我真的不是抄袭，我真的是自己想出来的，不过我感觉这就是一个很简单的优化方法应该会有很多人想到一起去吧。
8皇后问题描述
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n1×n1，而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解。

八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。

艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。

八皇后问题出现在1990年代初期的著名电子游戏第七访客中。
问题描述
下面的代码是我在写作业之前在网上找资料时发现的回溯法求解8皇后问题的代码

下面的代码改写自刘汝佳《算法竞赛入门经典》

来源博客连接：https://www.cnblogs.com/bigmoyan/p/4521683.html
void queen(int row){
    if(row==n)
        total++;
    else
        for(int col=0;col!=n;col++){
            c[row]=col;
            if(is_ok(row))
                queen(row+1);
        }        
}

这种简单的回溯法求解八皇后问题时会进行很多无效的搜索。如下图中情况


如上图，已经放置了四个皇后，但此时第六行全部处于皇后的攻击区域，但原始的回溯算法还会继续搜索第五层的两个位置，即使这种放置情况已经不存在可行解。
还有下图中的情况


此时下面的四行都可以放置皇后，但是最后一列已经全部处于皇后的攻击位置，不能继续放置皇后了（这个地方我也做了一下优化，但是不知道为什么实际运行时间几乎没有什么变化，我分析主要原因可能是我写水平有限，没有正确实现，导致这一段代码可能没有起到任何作用，其次可能是这种情况出现的概率不多，所以优化效果不明显，不过后一种情况我并没有仔细的分析，只是想了一下问题的可能性）
优化思路
若将整个棋盘表示为一个矩阵，则在每次放下皇后时，将棋盘上皇后可以攻击的位置进行标注，在每次放下皇后之后，检查剩余的行和列是否可以继续放下皇后，若存在某一行均处在皇后的攻击范围内，则退回下一步，搜索下一个位置，通过增加一个判定函数可以有效减少无效的搜索分支，该种方法可以预先判断棋盘的可摆放位置。提高算法的效率。例如在下图的情况下，当前搜索分支已经不存在可行解时，停止对当前分支的搜索，直接搜索下一个分支。



此时通过判定函数已经确定前四个皇后的摆法已经不存在可行解，于是继续搜索第四行的下一个位置而不去搜索第五行。
实现代码
/*这个是我写的最原始的回溯法求解的代码*/
void Queens1(int floor){
 if(floor==n)
  total++;
 else{
  for(int i=0;i<n;i++){
   if(ChkBoard[floor][i]==0){
    res[floor]=i;
    ChangeChkBoard(floor,i,true);
    Queens1(floor+1);
    ChangeChkBoard(floor,i,false);
   }
  }
 }
}

/*这里是优化后的代码*/
void Queens2(int floor){
 if(floor==n)
  total++;
 else{
  for(int i=0;i<n;i++){
   if(ChkBoard[floor][i]==0){
    res[floor]=i;
    Board[i]=false;
    if(!ChangeChkBoard(floor,i,true)){//将棋盘进行标注，并判断是否有解
     ChangeChkBoard(floor,i,false);//清除标记操作
     Board[i]=true;
     continue;
    }
    else{
     Queens2(floor+1);//搜索下一层
     ChangeChkBoard(floor,i,false);//清除标记
     Board[i]=true;
    }
   }
  }
 }
}


/*这个函数中包含了每次放下皇后后标记攻击位置的代码以及剪枝的代码*/
/*当时写作业的时候就直接写在一起了*/
bool ChangeChkBoard(int row,int col,bool key){
	//在每次放下皇后后在棋盘上标注皇后的攻击范围
	int row1=row,col1=col;
	
	//由key的值判断在棋盘上标注还是清除标注
	if(key){
		for(int i=0;i<n;i++){
		ChkBoard[row][i]+=1;
		ChkBoard[i][col]+=1;
		}
		//横行和竖行

		row=row1;
		col=col1;
		while(row>=0&&col>=0){
			ChkBoard[row--][col--]+=1;
		}
		//对角线左上

		row=row1;
		col=col1;
		while(row<n&&col<n){
			ChkBoard[row++][col++]+=1;
		}
		//对角线右下

		row=row1;
		col=col1;
		while(row<n&&col>=0){
			ChkBoard[row++][col--]+=1;
		}
		//对角线左下

		row=row1;
		col=col1;
		while(row>=0&&col<n){
			ChkBoard[row--][col++]+=1;
		}
		//对角线右上
		
		ChkBoard[row1][col1]-=5;
		//消除中心点重复标记
	}
	else{
		for(int i=0;i<n;i++){
			ChkBoard[row][i]-=1;
			ChkBoard[i][col]-=1;
		}

		row=row1;
		col=col1;
		while(row>=0&&col>=0){
			ChkBoard[row--][col--]-=1;
		}

		row=row1;
		col=col1;
		while(row<n&&col<n){
			ChkBoard[row++][col++]-=1;
		}

		row=row1;
		col=col1;
		while(row<n&&col>=0){
			ChkBoard[row++][col--]-=1;
		}

		row=row1;
		col=col1;
		while(row>=0&&col<n){
			ChkBoard[row--][col++]-=1;
		}

		ChkBoard[row1][col1]+=5;
	}

	//对剩下的n-row1行进行判断是否有某一行均处在攻击范围内
	bool flag=true;
	if(key&&((row1+1)<n)&&(row1>=(n/2))){
		for(int i=row1+1;i<n;i++){
			flag=false;
			for(int j=0;j<n;j++){
				if(ChkBoard[i][j]==0){
					flag=true;
					break;
				}
			}
			if(!flag)
				break;
		}
	}
	//flag=true时表示可以继续进行，flag=false时表示某一行被占满
	return flag;
	
}


运行效果


这个图我直接从我写的报告里截过来了，可以看出来差不多节省了1/5的时间左右，效果还是不错的，超出了我之前的想象。

初级8皇后问题，不是真正的8皇后问题，是该问题的初级条件限制：产生不同行，不同列的组合。
typedef struct Spoint
{
	int x;
	int y;
	Spoint()
	{
		x = -1;
		y = -1;
	}
};

static Spoint point[8];

int Queen8(int n, int cur)
{

	static  int iCount = 0;
	if(cur == n)
	{   
		iCount++;

		for(int i = 0; i < n; i++)
		{
			printf("(%d,%d) ", point[i].x, point[i].y);

		}

		printf("\n");

	}
	else
	{
		for(int i = 0; i < n; i++)
		{
			bool bNextRow = false;
			for(int j = 0; j < n; j++)
			{
				
					int bShow = false;	

					for(int k = 0; k < cur; k++)
					{
						if(i == point[k].x )
						{
							bNextRow = true;
							break;
						}	
						if(j == point[k].y)
						{
							bShow = true;
							break;
						}
					}

					if(bNextRow)
					{
						bNextRow = false;
						break;
					}

					if(!bShow)
					{
						
						bShow = false;
						point[cur].x = i;
						point[cur].y = j;
						Queen8(A, n, cur + 1);
					}
				
			
			}

		}
	}
	return iCount;
}

int WQueen8_Train()
{
	int cur = 0;
	int n = 8;
	
	int *B = (int *)malloc(n * sizeof(int));
	memset(B, 0, n *  sizeof(int));	 

	int num = Queen8(n, cur);
	delete [] B;
	return num;
}

8皇后问题
时限：1000ms 内存限制：10000K 总时限：3000ms
描述：

输出8皇后问题所有结果。

输入：

没有输入。

输出：

每个结果第一行是No n：的形式，n表示输出的是第几个结果；下面8行，每行8个字符，‘A’表示皇后，‘.’表示空格。不同的结果中，先输出第一个皇后位置靠前的结果；第一个皇后位置相同，先输出第二个皇后位置靠前的结果；依次类推。

输入样例：


输出样例：

输出的前几行：
No 1:
A.......
....A...
.......A
.....A..
..A.....
......A.
.A......
...A....
No 2:
A.......
.....A..
.......A
..A.....
......A.
...A....
.A......
....A...


#include<stdio.h>
#include<math.h>
int a[8],n=1;
void search(int m);
void output(int s[8]);
int panduan(int m,int n);
int main()
{
	search(0);
	return 0;
}


void search(int m)
{
	int i,row,col,flag;
	if(m==8)
	{
		output(a);
	}
	else
	for(i=0;i<8;i++)
	{
		a[m]=i;
		flag=panduan(m,i);
		if(flag==1)
		{
			search(m+1);
		}
	}
}


int panduan(int row,int col)
{
	int i,flag=1;
	for(i=0;i<row;i++)
	{
		if(a[i]==col||row-i==abs(col-a[i]))
		{
			flag=0;
			break;
		}
	}
	return flag;
}


void output(int s[8])
{
	int i,j;
	printf("No %d:\n",n);
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			if(j==s[i])printf("A");
			else printf(".");
			if(j==7)printf("\n");
		}
	}
	n++;
}