打印到类阵列的给定序列的所有排列的n皇后问题

题目例如以下：Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

---

分析：假设仅仅是求排列数非常好算，可是要打印全部排列且不反复比較困难。

假设单纯用for循环或递归。非常easy出现死循环。

而假设用随机生成排列，直到打印出全部排列。又easy超时。

        因此通过对问题的分析，发现能够将原问题映射成为n皇后问题。每一次排列映射为n皇后的一次成功摆放，打印全部的排列即打印全部摆放皇后的方法。但与n皇后问题不同的是。此问题皇后不能放在同行同列，却能够放在对角线。因此核心还是回溯法，代码例如以下：
import java.util.ArrayList;
import java.util.Stack;
public class Main {
    public static void main(String[] args)
    {
        int[] num={1};
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        result=permute(num);
        System.out.print(result);
    }
    public static ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> elem=new ArrayList<Integer>();
        int QueueNum=num.length;
        Stack<Integer> QueuePos=new Stack<Integer>();
        if(num.length==0)
            return result;
        if(num.length==1)
        {
            elem.add(num[0]);
            result.add(elem);
            return result;
        }
        int row;
        QueuePos.push(0);
        row=0;
        while(row>=0)
        {
            put_queue(QueuePos,row,QueueNum);
            //皇后放置完成
            for(int i=0;i<QueuePos.size();i++)
            {
                elem.add(num[QueuePos.get(i)]);
            }
            result.add(elem);
            elem=new ArrayList<Integer>();
            //寻找下一个方法
            row=find_next(QueuePos,QueueNum);
            //status=put_queue(QueuePos,row,QueueNum);
        }
        return result;
    }
    
    public static int find_next(Stack<Integer> QueuePos,int QueueNum)
    {
        int row,column;
        row=QueueNum-2;
        QueuePos.pop();
        column=QueuePos.pop();
        column=column+1;
        while(row>=0)
        {
            
            if(column<QueueNum&&!QueuePos.contains(column))
            {
                QueuePos.push(column);
                return row;
            }
            else if(column==QueueNum)
            {
                row--;
                if(row<0)
                    return row;
                column=QueuePos.pop();
                column=column+1;
            }else
            {
                column++;
            }
        }
        return row;
    }
    
    public static boolean put_queue(Stack<Integer> QueuePos,int row,int QueueNum)
    {
        int i,j,column; //i代表行。j代表列
        i=row+1;
        while(i<QueueNum)
        {
            for(j=0;j<QueueNum;j++)
                if(!QueuePos.contains(j))
                    break;
            if(j!=QueueNum)
            {
                QueuePos.push(j);
                i++;
                j=0;
            }
            else
            {
                i--;
                if(i>=0)
                {
                    column=QueuePos.pop();
                    QueuePos.push(column+1);
                }else
                    return false;
            }
        }
        return true;
    }
}

版权声明：本文博主原创文章。博客，未经同意不得转载。

转载于:https://www.cnblogs.com/zfyouxi/p/4828498.html

总结

以上是生活随笔为你收集整理的打印到类阵列的给定序列的所有排列的n皇后问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。