算法介绍

回溯法：

回溯法又称试探法。回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。
回溯算法的基本思想：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

问题实例

问题描述：

题目：
要求用回溯法求解 8-皇后问题，使放置在 8*8 棋盘上的 8 个皇后彼此不受攻击，即：任 何两个皇后都不在同一行、同一列或同一斜线上。请输出 8 皇后问题的所有可行解。

问题分析

在解决八皇后问题时，如果采用穷举法，则需要列举8^8种情形。采用回溯法，则是对解空间使用深度优先遍历的方式找到可行解，然后用限制条件来缩小解空间。
伪代码：
①设一数组 x[]，下标代表第几行，值代表该行中的那一位置。设一变量k，代表此时在下第几行。
②设一个判断是否符合条件（不同列，不在对角线上）的函数，利用列不能相同，列之差与行之差不能相同判断，不符合条件的直接跳过（缩小解空间）
③利用for循环，将符合条件的可行解放入x [ ] 中，当x [ ]填满后，输出，此时一种方案结束。
④利用递归，直到所有可行方案输出，结束。

代码：

#include <iostream>
#include <cmath>
using namespace std;
int num=0;
bool Wzhi(int k,int i,int *x)
{
    for(int j=0;j<k;j++) //j此时代表第几行
        if(   (i==x[j]     )||(        abs(k-j) == abs(i-x[j])       ))
//          判断是否同一列     判断是否在对角线上（利用两直角边长度相同）
        {
            return false;
        }

    return true;
}
void Bhh (int k,int n,int *x)
{
    for(int i=0;i<n;i++)
    {
        if(Wzhi(k,i,x))
        {
            x[k]=i;
            if(k==n-1)
            {
                for(int i=0;i<n;i++)
                {
                    cout<<x[i]<<" ";
                }
                num++;
                cout<<endl;
            }
            else
            {
                Bhh(k+1,n,x);
            }
        }

    }
}
void Bhh (int n,int *x)
{
    Bhh(0,n,x);
}

int main()
{
    int x[8];//下标代表第几行，值代表放在该行哪个位置
    int n=8;
    for(int i=0;i<n;i++)
    {
        x[i]=-1;
    }
    Bhh(8,x);
    cout<<"共计有"<<num<<"种组合"<<endl;
}

结果：

解决该问题的关键是利用for循环作深度优先遍历，对第k行的每一格进行逐一判断，判断该格是否满足0 ~ k-1 行不同列，不在对角线的条件，不满足直接舍弃，否则利用递归继续选择合适的位置。

记录整理一些学习中的问题，如果有不恰当和错误的地方，欢迎批评指正~

回溯法——8皇后问题

一、实验内容

1.问题描述
要求用回溯法求解8 —— 皇后问题，是放置在8*8棋盘上的8个皇后彼此不收攻击，即：任何两个皇后都不在同一行、同一列和同一斜线上。
请输出8皇后问题所有可行解。
2、要求
（1）写出问题分析过程
（2）写出程序代码
（3）写出程序运行结果

二、程序代码

package huisu;

public class Queen {

	/*
	 * 一共有多少个皇后（此时设置为8皇后在8*8棋盘，可以修改此值为N皇后
	 */
	int max= 8;
	static long sum=0;
	
	/*
	 * 该数组保存结果，第一个皇后摆在array[0]列，第二个摆在array[1]列，
	 */
	int [] array = new int[max];
		
	public static void main(String[] args) {
		new Queen().check(0);
		System.out.println("一共有:"+sum+"个可行解");
		
	}
	
	/*
	 * n代表当前是第几个皇后
	 * @param n
	 * 皇后n在array[n]列
	 */
	private void check(int n) {
		//终止条件是最后一行已经摆完，由于每摆一步都会教研是否有冲突，所以就进行下一行逻辑
		
		if(n==max)
		{
			sum++;
			print();
			return;
		}
		for(int i=0;i<max;i++)
		{
			array[n] = i;
			if(judge(n)) {
				check(n+1);
			}
		}
	}
	
	private boolean judge(int n) {
		for(int i=0;i<n;i++)
		{
			if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i] )) {
				return false;
			}
		}
		return true;
	}
	
	private void print() {
		for(int i=0; i < array.length;i++)
		{
			System.out.print(array[i]+1+" ");
		}
		
		System.out.println();
		
	}

}

三、程序运行结果

题目描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

输入

一个整数n（ 1 < = n < = 10 )

输出

每行输出对应一种方案，按字典序输出所有方案。每种方案顺序输出皇后所在的列号，相邻两数之间用空格隔开。如果一组可行方案都没有，输出“no solute!”

样例输入

4

样例输出

2 4 1 3
3 1 4 2

分析

n皇后问题实际上是一个全排列+筛选的问题，n皇后会生成一个数组，数组下标表示第几列，而数组内容表示第几行，比如四皇后排列2413表示如图所示

n皇后的是否合法的判断条件是是否有两个皇后在一条对角线上。是否在对角线上，可以通过判断，两个皇后的行列位置差是否相等，即两者行相减的绝对值和列相减的绝对值是否相等，来判断是否在对角线上。
因此，这道题的思路是给出n个数的所有排列组合，然后对这些全排列进行判断，合法的话，计数器+1，打印出排列顺序。

代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int arr[10]={0};
bool isLegal(int arr[],int n)//判断是否合法
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(abs(i-j)==abs(arr[i]-arr[j]))//判断是否在对角线上
                return false;
        }
        
    }
    return true;
}

void showArray(int arr[],int n)//输出排列结果
{
    for(int i=1;i<=n;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

int main(){
    
    int n;
    while(cin>>n)
    {
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            arr[i]=i;
        }
        do{
            if(isLegal(arr,n)){
                cnt++;
                showArray(arr,n);
            }
        }while(next_permutation(arr+1,arr+n+1));//全排列
        if(cnt==0)
            cout<<"no solute!"<<endl;
    }

    return 0;
}