首页 > 试题广场 >

八皇后问题

[编程题]八皇后问题
  • 热度指数：598 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将 8 个皇后放在棋盘上（有8×8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即 a=b1b2...b8, 其中bi（1≤bi≤8）为相应摆法中第 i 行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数n，要求输出第n个串。串的比较是这样的:皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

输入描述:
输入包含多组数据。

每组数据包含一个正整数n（1≤n≤92）。


输出描述:
对应每一组输入，输出第n个皇后串。
示例1

输入

1
92

输出

15863724
84136275
算法知识视频讲解
添加回答
拉格朗日无悔头像 拉格朗日无悔 
/*递归求出符合要求的串，思路比较清晰*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

bool isOK(string queen)  //判断一个串各皇后位置是否冲突
{
    for (int i = 0; i < queen.size(); i++)
    {
        for (int j = i + 1; j < queen.size(); j++)
        {
            if (j - i == (queen[j] - '0') - (queen[i] - '0') || j - i == (queen[i] - '0') - (queen[j] - '0'))
                return false;
        }
    }
    return true;
}

void getQueen(string queen, int begin, vector<string>& queen_list)  //求一个串排除皇后位置冲突后的全排列
{
    if (begin == queen.size() - 1  && isOK(queen)) queen_list.push_back(queen);
    for (int i = begin; i < queen.size(); i++)
    {
        if (i != begin && queen[i] == queen[begin]) continue;
        swap(queen[begin], queen[i]);
        getQueen(queen, begin + 1, queen_list);
        swap(queen[begin], queen[i]);
    }
}

int main()
{
    vector<string> res;
    string queen = "12345678";
    getQueen(queen, 0, res);
    sort(res.begin(), res.end());
    int b;
    while (cin >> b)
    {
        int sum = 0, len = res[b - 1].size() - 1;
        for (int i = 0; i <= len; i++) 
            sum += (res[b - 1][len - i] - '0') * pow(10, i);
        cout << sum << endl;
    }
    system("pause");
    return 0;
}
发表于 2019-03-17 21:57:02 回复(0)
Java
kestars头像 kestars 
 import java.util.*;
public class Main{
    static int n;
    static int[] x;
    static long sum;
    static ArrayList<Integer> arrayList=new ArrayList<Integer>();

    public static long nQueen(int nn){
        n=nn;
        x=new int[n+1];
        sum=0;
        backtrack();
        return sum;
    }

    public static void backtrack(){
        x[1]=0;
        int k=1;
        while(k>0){
            x[k]+=1;
            while((x[k]<=n) && !place(k))
                x[k]+=1;
            if(x[k]<=n){
                if(k==n){
                    String str="";
                    for(int i=0;i<=n;i++){
                        str+=x[i];
                    }
                    int number=Integer.valueOf(str);
                    arrayList.add(number);
                }
                else{
                    k++;
                    x[k]=0;
                }
            }else
                k--;
        }
    }

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


    public static void main(String[] args){
        int n=8;
        nQueen(8);
        Collections.sort(arrayList);
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            int index=scanner.nextInt();
            System.out.println(arrayList.get(index-1));
        }
    }
}

发表于 2018-09-19 14:58:02 回复(0)
Java
詆調壹點头像 詆調壹點 
import java.util.*;
public class Main {
    public static List<String> list = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] arr = new int[8][8];
        eight_queen(arr, 0, "");
        while (sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println(list.get(n - 1));
        }
    }

    public static void eight_queen(int[][] arr, int row, String s) {
        if(row > 7) list.add(s);
        for (int i = 0; i < 8; i ++) {
            if(check(arr, row, i)) {
                arr[row][i] = 1;
                eight_queen(arr, row + 1, s + (i + 1));
                arr[row][i] = 0; // 回溯
            }
        }
    }

    public static boolean check(int[][] arr, int row, int col) {
        // 检查列
        for (int i = 0; i < 8; i ++) {
            if(arr[i][col] == 1) return false;
        }
        // 检查右上到左下斜线
        for (int i = row - Math.min(row, 7 - col), j = col + Math.min(row, 7 - col); i < 8 && j >= 0; i ++, j --) {
            if(arr[i][j] == 1) return false;
        }
        // 检查左上到右下斜线
        for (int i = row - Math.min(row, col), j = col - Math.min(row, col); i < 8 && j < 8; i ++, j ++) {
            if(arr[i][j] == 1) return false;
        }
        return true;
    }
}

编辑于 2017-11-26 21:07:13 回复(0)
C/C++
Cavs头像 Cavs 
我把之前的n皇后拿过来改了改 
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
#define INF 1000000
using namespace std;
class Queens {
public:
 typedef pair<double, double> Pair;
 vector<vector<Pair>> res;
 bool checkAttack(int x, int y, vector<Pair>& place)
 {
  if (place.empty()) return false;
  for (auto& pr : place)
  {
   if (x == pr.first || y == pr.second || abs(x - pr.first) == abs(y - pr.second))
    return true;
  }
  return false;
 }
 void DFS(int n, int level, vector<Pair>& place)
 {
  if (level >= n)
  {
   res.emplace_back(place);
   return;
  }
  for (int i = 0; i < n; ++i)
  {
   if (!checkAttack(level, i, place))
   {
    place.emplace_back(level, i);
    DFS(n, level + 1, place);
    place.pop_back();
   }
  }
 }
 void nQueens(int n)
 {
  vector<Pair> place;
  place.reserve(n);
  DFS(n, 0, place);
 }
};
 int main(int argc, char** argv)
{
 //freopen("in.txt", "r", stdin);
 Queens s;
 s.nQueens(8);
 int n;
 while (cin >> n && n > 0 && n <= 92)
 {
  for (auto& i : s.res[n - 1])
   cout << i.second + 1;
  cout << endl;
 }
 return 0;
}

发表于 2017-07-18 16:37:21 回复(0)
doodle777头像 doodle777
根据此文通过位运算求八皇后解，然后将序列插入到vector内再输出。
http://blog.csdn.net/kai_wei_zhang/article/details/8033194 
#include<iostream>
#include <vector>
#include <map>
using namespace std;

vector<vector<int> > table;
vector<int> list(8);
map<int, int> mp;
void initMap()
{       // 将二进制的列信息转化为十进制的列号，建立此映射
	int a = 1;
	for (int i = 0; i < 8; ++i)
		mp[a << (7 - i)] = i;
}

void eigheQueue(int row, int ld, int rd, int cnt)
{
	int pos, p;

	if (row != (1 << 8) - 1)
	{
		pos = ((1 << 8) - 1) & (~(row | ld | rd));
		while (pos)
		{
			p = pos & (~pos + 1);
			pos = pos - p;
			list[cnt] = mp[p] + 1;
			eigheQueue(row | p, (ld | p) << 1, (rd | p) >> 1, cnt + 1);
		}
	}
	else table.insert(table.begin(), list);
}

int main()
{
	initMap();
	eigheQueue(0, 0, 0, 0);

	int n;
	while (cin >> n)
	{
		for (auto i : table[n - 1]) cout << i;
		cout << endl;
	}

	return 0;
}

发表于 2015-12-17 17:02:54 回复(0)
牛客145121328号头像 牛客145121328号
/* 思路：
1） 全排列：就是所有皇后都不在同一行或列；参见：
    sort_vec()
2）其中，位置的值相减的绝对值，不等于位置差的绝对值，那么就是不在一条斜线上；参见：
    check_valid()
3）把结果排序，按位置输入即可；
*/

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

inline bool check_valid(const vector<int>& data_vec)
{
    for (size_t i = 0; i < data_vec.size(); ++i) {
        for (size_t j = i + 1; j < data_vec.size(); ++j) {
            if (data_vec[i] - data_vec[j] == i - j
                || data_vec[i] - data_vec[j] == j - i) {
                return false;
            }
        }
    }
    return true;
}

inline int get_value(const vector<int>& data_vec)
{
    int ret = 0;
    int multi = 10000000;
    for (size_t i = 0; i < data_vec.size(); ++i) {
        ret += data_vec[i] * multi;
        multi /= 10;
    }
    return ret;
}

// 从i 到 j 全排列
void sort_vec(vector<int>& data_vec, int i, int j, vector<int>& ret_vec)
{
    if (i == j) {
        if (check_valid(data_vec)) {
            int ret = get_value(data_vec);
            ret_vec.push_back(ret);
        }
        return;
    }

    for (int t = i; t < j; ++t) {

        swap(data_vec[i], data_vec[t]);

        sort_vec(data_vec, i + 1, j, ret_vec);

        swap(data_vec[i], data_vec[t]);
    }
}


int main()
{
    const int N = 8;
    vector<int> data_vec = { 1, 2, 3, 4, 5, 6, 7, 8 };

    vector<int> ret_vec;
    sort_vec(data_vec, 0, N, ret_vec);

    std::sort(ret_vec.begin(), ret_vec.end());
    int pos = 0;
    while (cin >> pos) {
        cout << ret_vec[pos - 1] << endl;
    }
    return 0;
}
发表于 2021-11-16 17:07:40 回复(0)
C/C++
牛客611924904号头像 牛客611924904号 
// write your code here cpp
#include
using namespace std;
vector> ans;
int c[9];
int vis[3][20];
void serach(int  cur)
{
    if(cur == 8)
    {
        vectortp;
        for(int i = 0;i<8;i++)
        tp.push_back(c[i]+1);
        ans.push_back(tp);

    }

    for(int i = 0;i<8;i++)
    {
        if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+8])
        {
            c[cur] = i;
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+8] = 1;

            serach(cur+1);
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+8] = 0;

        }
    }

}
int main()
{
    int n;
    string temp;
    while(scanf("%d",&n)!= EOF)
    {
        memset(vis,0,sizeof(vis));
        memset(c,-1,sizeof(c));
        serach(0);
        for(auto it:ans[n-1])
        {
           cout<<it;
        }
        cout<<endl;

    }
}

这应该是比较精简的代码了。模板来自刘汝佳的算法入门第二版的424页，该算法模板的简单，思路也很简单，代码简单了之后，思路就会更加清晰。

编辑于 2021-08-31 19:25:06 回复(0)
张强201810222256310头像 张强201810222256310

python代码

import sys

MAX = 8 
queen = [0] * MAX * MAX
valid = [0] * MAX 
solutions = []
count = 1


def putQueen(row):
    global count
    for i in xrange(MAX):
        if queen[row*MAX + i] == 0:
            valid[row] = i + 1
            mark = setMark(row, i)
            if row == MAX - 1:
                solutions.append(sumValue(valid))
            else:
                putQueen(row+1)
            unSetMark(mark)


def setMark(row, col):
    """mark"""
    mark = []

    for i in xrange(MAX):
        if queen[row*MAX + i] ==0:
            queen[row*MAX + i] = 1
            mark.append((row, i))

    for i in xrange(row, MAX):
        if queen[i*MAX + col] ==0:
            queen[i*MAX + col] = 1
            mark.append((i, col))

    r, c = row, col
    while r < MAX and c < MAX:
        if queen[r*MAX + c] == 0:
            queen[r*MAX + c] = 1
            mark.append((r, c))
        r += 1
        c += 1

    r, c = row, col
    while r < MAX and c >= 0:
        if queen[r*MAX + c] == 0:
            queen[r*MAX + c] = 1
            mark.append((r, c))
        r += 1
        c -= 1

    return mark


def unSetMark(mark):
    for row, col in mark:
        queen[row*MAX + col] = 0

def sumValue(nums):
    sum = 0
    for num in nums:
        sum = sum * 10 + num

    return sum

putQueen(0)
solutions.sort()

num = sys.stdin.readline()
while num:
    print solutions[int(num.strip())-1]
    num = sys.stdin.readline()
发表于 2018-10-27 12:06:39 回复(0)
牛客1610600号头像 牛客1610600号

思路：全排列--> 找出符合要求的--> 排序-->直接取出

#include
using namespace std;
bool compare(vector &a){ //确认本顺序是否符合要求

    for(int i=0;i<a.size();i++){
        for(int j=i+1;j<a.size();j++)
        {
            if((i-j)==a[i]-a[j] || (j-i)==a[i]-a[j])
                return false;

        }

    }
    return true;

}   
void find_all(vector> &n,vector &a,int begin){ // 找到所有的可能排列

    int tmp = a[begin];
    if(begin==a.size()-1){

        if(compare(a)){

           //printVector(a);
           //printf("\n");
           n.push_back(a);
        }
        else{
            //printVector(a);
            //printf("\n");
        }
    }

    else{   

    for(int i=begin;i<a.size();i++){
        vector b(a); //保持在a上进行互相交换
        b[begin] = b[i];
        b[i] = tmp;
        find_all(n,b,begin+1);
    }
    }
}
vector trans(vector> &N){ //将二维数组转换成一维数组，方便后面排序
    vector R;
    for(int i=0;i<N.size();i++){
        int sum=0;
        //printVector(N[i]);
        for(int j=0;j<N[0].size();j++){

           sum+=N[i][j]*(int)pow(10.0,1.0*(N[0].size()-j-1));
           //printf("sum = %d , ",sum);
        }
     //printf(" %d\n",sum);
     R.push_back(sum); 
    }

    return R;
}
int main(){
    // 初始a[] = {1,2,3,4,5,6,7,8}
    int a[8]={1,2,3,4,5,6,7,8};
    vector A(&a[0],&a[8]);
    vector> N;
    find_all(N,A,0);
    //printf("%ld\n",N.size());
    vector R;
    R = trans(N);
    sort(R.begin(), R.end(),less());//升
    //printf("%d",R[9]);
    int num;
    while(scanf("%d",&num)!=EOF){

       printf("%d\n",R[num-1]);

    }

    /*scanf("%d",&n);
    int *num= new int[n];
    for(int i=0;i<n;i++)
        scanf("%d",&num[i]);
    for(int i=0;i<n;i++)
        printf("%d\n",R[num[i]-1]);
    */
    return 0;
}
发表于 2017-09-19 19:21:52 回复(0)
C/C++
月晕潆洄头像 月晕潆洄
#include<iostream>
#include<string>
using namespace std;
int chessboard[8][8],sum=0;
string queen,answer[100];
void chess(int raw){
    if(queen.length()==8){
        sum++;
        answer[sum]=queen;
        return;
    }
    else{
        for(int i=0;i<8;i++){
            if(chessboard[raw][i]==0){
                queen+=char(i+49);
                for(int j=0;j<8;j++){
                    chessboard[j][i]++;
                }
                for(int j=1;j<8;j++){
                    if(raw+j<8 && i+j<8) chessboard[raw+j][i+j]++;
                    if(raw+j<8 && i-j>=0) chessboard[raw+j][i-j]++;
                    if(raw-j>=0 && i-j>=0) chessboard[raw-j][i-j]++;
                    if(raw-j>=0 && i+j<8) chessboard[raw-j][i+j]++;
                }
                chess(raw+1);
                for(int j=1;j<8;j++){
                    if(raw+j<8 && i+j<8) chessboard[raw+j][i+j]--;
                    if(raw+j<8 && i-j>=0) chessboard[raw+j][i-j]--;
                    if(raw-j>=0 && i-j>=0) chessboard[raw-j][i-j]--;
                    if(raw-j>=0 && i+j<8) chessboard[raw-j][i+j]--;
                }
                for(int j=0;j<8;j++)
                    chessboard[j][i]--;
                queen=queen.substr(0,queen.length()-1);
            }
        }
    }
}
int main(){
    int n;
    chess(0);
    while(cin>>n)
        cout<<answer[n]<<endl;
    return 0;
}

c代码...很垃圾的全模拟，完全看不懂1楼在写什么，这就是差距吧T T.
大概意思就是按行一层层递归深搜，每一次把能吃掉的地方全部标记，然后回溯，这样一定能保证找到的解是递增的，把所有的解都存在answer数组里，要找哪一个直接查找就好了
发表于 2017-06-13 11:31:55 回复(0)
aaaaaaddddddwerfv头像 aaaaaaddddddwerfv 
import java.util.*;

public class Main {
	public static int[][] visited = new int[3][15];
	public static int curCount=0; 

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			help(0,n,new String());// 回溯求子串
		}
	}

	// 回溯法求子串,因为是有序的，所以直接打印出第n个子串
	public static int help(int curRow,int n,String sb) {
		if (curRow == 8) {
			if(++curCount==n){
				System.out.println(sb);
				curCount=0;
				return 0;
			}
			return 1;
		}
		int reslut=1;
		for (int curCol = 0; curCol < 8; curCol++) {
			if (visited[0][curCol] == 0 && visited[1][curRow - curCol + 7] == 0
					&& visited[2][curRow + curCol] == 0) {
				visited[0][curCol] = 1;
				visited[1][curRow - curCol + 7] = 1;
				visited[2][curRow + curCol] = 1;
				reslut=help(curRow + 1,n,sb + (curCol + 1));
				visited[0][curCol] = 0;
				visited[1][curRow - curCol + 7] = 0;
				visited[2][curRow + curCol] = 0;
				if(reslut==0)
					break;
			}
		}
		return reslut;
	}

}

发表于 2017-03-31 11:47:26 回复(0)
Vurtne头像 Vurtne
http://www.matrix67.com/blog/archives/266
不知道需不需要贴代码，m67这篇博客介绍的很详细了，在他基础上改动了一下写了个java版的
发表于 2015-01-04 20:31:12 回复(0)
提交观点

问题信息

查找
难度：
12条回答 10075浏览

热门推荐

通过挑战的用户

查看代码

相关试题

八皇后问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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