首页 > 试题广场 >

将9个石子放在9x9的方格中，要求同行、同列、45度上无两个

[问答题]
将9个石子放在9x9的方格中，要求同行、同列、45度上无两个石子。
添加回答
牛客787908号头像 牛客787908号
本题目答案为：352
本题目解答思路：N后问题，所采用回溯法，递归函数BackTrack(1)实现对整个姐空间的回溯搜索，BackTrack搜索空间的第i层子树。类Queen的数据成员记录姐空间中结点信息，以减少传给BackTrack的参数，sum记录当前已找到的可行方案数。通用源代码如下：
import java.util.Scanner;

public class Queen {
static int n;// 皇后个数
static long sum;// 当前解个数；
static int[] x;

public static void BackTrack(int t) {
if (t > n) {
sum++;
} else {
for (int i = 1; i <= n; i++) {
x[t] = i;
if (Place(t))
BackTrack(t + 1);
}
}
}

public static boolean Place(int k) {
for (int j = 1; j < k; j++)
if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k]))
return false;
return true;

}

public static void main(String[] args) {
// 输入皇后的个数
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String str = in.nextLine();
if (str != null) {
n = Integer.parseInt(str);
sum = 0;
x = new int[n + 1];
for (int i = 0; i <= n; i++)
x[i] = 0;
BackTrack(1);
System.out.println(sum);
} else {
System.out.println("请输入正确的数字~");
}

}
}

}


编辑于 2016-01-12 13:39:01 回复(0)
更多回答
90s头像 90s
答案是 352 
9*9是个完全对称的么 
但是如果把对称的和旋转的解去掉的话 还剩46个 完全不一样的解
下面给出 八皇后问题的百度百科
和一种c代码

这是一个很著名问题的变形 可以搜搜 八皇后问题 八皇后问题的题目是八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。 所以这个题的  下面是解法 #include#includeusing namespace std; void backtrack(int, vector, int, int); bool place(int, vector); void displayqueen(vector, int, int); int sum = 0; int main(void) { int N; int kind; cout<<"请输入皇后的个数："; cin>>N; vectorx(N+1,0); cout<<"----------------------------------"<>kind; backtrack(1, x, N, kind); return 0; } void backtrack(int t, vectorx, int N, int kind) { if(t > N) { sum += 1; displayqueen(x, N, kind); } else { for(int i=1; i S(N+1, vector(N+1)); for(int i=1; i
编辑于 2015-01-28 15:47:46 回复(0)
提交观点

问题信息

智力题 迅雷
上传者：阳
难度：
2条回答 7275浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号