本文主要是介绍九度OJ 1254:N皇后问题 (N皇后问题、递归、回溯),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- 题目描述:
-
N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。
你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。
- 输入:
-
输入包含多组测试数据。
每组测试数据输入一个整数n(3<n<=13),表示有n*n的棋盘,总共摆放n个皇后。
- 输出:
-
对于每组测试数据,输出总共不同的摆放情况个数,结果单独一行。
- 样例输入:
-
4
- 样例输出:
-
2
思路:
N皇后问题的常规解法是试探回溯法,能够给出所有解。如果只要得到一个解就行,那么还有随机解法。
相比常规解法,更高效的是位运算解法。
两者的详细介绍见我的另一篇文章《N皇后问题算法》。
代码:
#include <stdio.h>int n, allPlacedState, count;void queen(int row, int ld, int rd)
{if (row != allPlacedState){int pos = allPlacedState & ~(row | ld | rd);while (pos){int p = pos & -pos;pos -= p;queen(row+p, (ld+p)<<1, (rd+p)>>1);}}else{count ++;}
}int main()
{while (scanf("%d", &n) != EOF){allPlacedState = (1<<n)-1;count = 0;queen(0, 0, 0);printf("%d\n", count);}return 0;
}
/**************************************************************Problem: 1254User: liangrx06Language: CResult: AcceptedTime:90 msMemory:912 kb
****************************************************************/
这篇关于九度OJ 1254:N皇后问题 (N皇后问题、递归、回溯)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!