首页 > 试题广场 >

八皇后问题

[编程题]八皇后问题

热度指数：595 时间限制：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

算法知识视频讲解

Java

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)