首页 > 搜索 > 回溯和剪枝 > 回溯法解n皇后问题
2013
12-13

回溯法解n皇后问题

这里说的回溯法其实就是递归的应用。遍历所有情况,每个都判断是否是解,然后输出符合情况的。
时间复杂度依然很高。

下面的程序读入一个n,然后输出n皇后的所有解。

详细注释见代码:

#include <iostream>
using namespace std;

int x[20]; //解向量
int sum; //可行方案个数
int n;

//在第t列是否可放置
bool place(int t){
	int i;
	for(i=1; i<t; i++)
		//如果 行-行 == 列-列 或者 在同一列。
		if(abs(t-i) == abs(x[t]-x[i]) || x[i]==x[t])
			return false;
	return true;
}

//回溯,即递归调用
void backtrack(int t){
	//cout << t << endl;
	int i;
	//到达最后一行,即找到所有解
	if(t > n){
		sum++;
		for(i=1; i<=n; i++)
			printf(" %d",x[i]);
		printf("\n");
	}else{
		//从第一行第一列开始,循环到 第一行 第n列
		for(i=1; i<=n; i++){
			x[t] = i; //对于第t行,第i列,放置皇后.

			//判断刚才放置的位置(x[t] = i)是否可行,如果可行,就放置下一行。
			//不可行的话,继续在第t行放置
			if(place(t))  backtrack(t+1);
		}
	}
}
int main(){
	while(cin >> n){
		backtrack(1); //从第1行开始
		cout << "方案数:" <<sum << endl; //可行解个数
	}
	
	return 0;
}

 


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. [email protected]

  3. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  4. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  5. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks