回溯算法（3）--n皇后问题及回溯法相关习题

一、n皇后问题

1、概述

        n皇后要求在一个n×n的棋盘上放置n个皇后，使得他们彼此不受攻击，皇后可以攻击同一行、同一列、同一斜线上的敌人，所以n皇后问题要求寻找在棋盘上放置这n个皇后的方案，使得任意两个皇后都不在同一行、同一列或同一斜线上。

2、子集树解法

（1）判断是否遍历过叶子结点（t>n），若没有则遍历子集树，判断place（t），即该层从1到n是否存在有成立的情况。

（2）place剪枝函数，遍历1到t，如果存在一个点满足同一列，同一对角线，那么舍弃这个叶节点，反之保留叶节点。由于每一层保存的点存放在x数组，该数组显性约束了不满足同一行的条件，数组中的索引+1就是行号，数组值为列号。

（3）若已经满足t>n，即已经遍历过叶子结点，则输出该可行解。

3、排列树解法

（1）判断是否遍历过叶子结点（t>n），若没有则遍历排列树，对后续层进行全排列，判断place（t），即该层从1到n是否存在有成立的情况。

（2）place剪枝函数，此时由于对后续层全排列，第一层的列数不能存在于后续层，不需要添加同一列的检查，其他与子集树一致。

（3）若已经满足t>n，即已经遍历过叶子结点，则输出该可行解。

4、代码

//n皇后问题
import java.util.Scanner;
public class Queen {
   static int x[]=new int[100];
   static int n;
   static int sum=0;
   public static void main(String [] args)
   {
        
        n=new Scanner(System.in).nextInt();
        //排列树提前添加x数组值，保证能够进行排列
        for(int i=1;i<=n;i++)
            x[i]=i;
        Backstack2(1);
   } 
   //子集树算法
   public static void Backstack(int t)
   {
        if(t>n)
        {
            sum++;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(x[i]==j)
                        System.out.print("Q ");
                    else    
                        System.out.print(". ");
                }
                System.out.println();
            }
            System.out.println();
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                x[t]=i;
                if(place(t))
                    Backstack(t+1);
            }
        }
   }
   public static boolean place(int t)
   {
        for(int i=1;i
            if((Math.abs(x[i]-x[t])==Math.abs(i-t))||x[i]==x[t])
                return false;
        return true;
   }
   //排列树算法
   public static void Backstack2(int t)
   {
        if(t>n)
        {
            sum++;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(x[i]==j)
                        System.out.print("Q ");
                    else    
                        System.out.print(". ");
                }
                System.out.println();
            }
            System.out.println();
        }
        else{
            for(int i=t;i<=n;i++)
            {
                
                swap(i,t);
                if(place2(t))
                    Backstack2(t+1);
                swap(i,t);
                
            }
        }
   }
   public static void swap(int i,int t)
   {
        int tmp=x[i];
        x[i]=x[t];
        x[t]=tmp;
   }
   public static boolean place2(int t)
   {
        for(int i=1;i
        {
            if(Math.abs(x[i]-x[t])==Math.abs(i-t))
                return false;
        }
        return true;
   }
}

5、结果

        通过Q和 . 区分皇后的位置。

二、含重复元素的全排列

1、概述

        给定一个可包含重复数字的序列，按任意顺序返回所有不重复的全排列，如：输入【1,1,2】，输出【1,1,2】，【1,2,1】，【2,1,1】。

2、算法

        排列树问题，在原有问题上添加条件x[t]==x[i]&&t!=i，当前交换的两个数若相同，且不是同一个数，则剪枝，注意循环中使用continue，表示下面的交换和扩展的操作不再进行，但循环继续。

3、代码

//含重复元素的全排列
import java.util.Scanner;
public class repeatperm {
   public static void main(String []args)
   {
        String m=new Scanner(System.in).nextLine();
        String []numbers=m.split("\\s+");
        
        int x[]=new int[numbers.length+1];
        for(int i=0;i
            x[i+1]=Integer.parseInt(numbers[i]);
        
        perm(x,1);
   } 
   //全排列
   public static void perm(int[] x,int t)
   {
        int n=x.length-1;
        
        if(t>n)
        {
            for(int i=1;i1;i++)
                System.out.print(x[i]+" ");
            System.out.println();
        }
        else
        {
            for(int i=t;i1;i++)
            {
                //约束条件，保证不再重复
                if(x[t]==x[i]&&t!=i)
                    continue;
                swap(t,i,x);
                perm(x,t+1);
                swap(t,i,x);
            }
        }
   }
   public static void swap(int t,int i,int []x)
   {
        int tmp=x[i];
        x[i]=x[t];
        x[t]=tmp;
   }
}

三、 组合

1、概述

        输入n和k，从1~n中任意不放回抽取k个值的所有情况，输入n=4，k=2，输出【1,2】，【1,3】，【1,4】，【2,3】，【2,4】，【3,4】。

2、算法

        子集树，在叶子结点未遍历结束前，每一层的值都为上一层的节点值到n之间所有的遍历。

3、代码

//组合问题
import java.util.Scanner;
public class combination {
    public static void main(String[] args)
    {
        int n=new Scanner(System.in).nextInt();  //n=4
        int k=new Scanner(System.in).nextInt();  //k=2
        int x[]=new int [k+1];
        combine(n,k,1,x);
    }
    public static void combine(int n,int k,int t,int x[])
    {
        if(t>k)
        {
            for(int i=1;i<=k;i++)
                System.out.print(x[i]+" ");
            System.out.println();
        }
        else
        {
            for(int i=x[t-1]+1;i<=n;i++)
            {
                x[t]=i;
                combine(n,k,t+1,x);
            }
        }
    }
}

四、组合总和

1、概述

        输入n和k，输出1-9的任取k个数的组合中，组合加和等于n的所有可能情况。

2、算法

        子集树算法，与上一道题相同，只需要在输出的时候，添加限制总和等于n的输出。另外可以进行改进，对于问题规模过大的情况，如果未完成的组合，组合总和已经大于等于n，则进行剪枝。

3、代码

//组合总和
import java.util.Scanner;
public class combinationsum {
   public static void main(String[] args)
    {
        int n=new Scanner(System.in).nextInt();  //n=7,判断条件和
        int k=new Scanner(System.in).nextInt();  //k=3
        int x[]=new int [k+1];
        combine(n,k,1,x);
    }
    public static void combine(int n,int k,int t,int x[])
    {
        if(t>k)
        {
            int sum=0;
            for(int j:x)
                sum+=j;
            if(sum==n)
            {
                for(int i=1;i<=k;i++)
                    System.out.print(x[i]+" ");
                System.out.println();
            }
        }
        else
        {
            for(int i=x[t-1]+1;i<=9;i++)
            {
                x[t]=i;
                combine(n,k,t+1,x);
            }
        }
    } 
}