# 回溯算法

## 1、八皇后问题

### 1.问题描述

​	在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即<font color='red'>任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法！</font>

### 2.分析

假设我们此时要在黑色方块的位置上面放置一个皇后：

![](one.png)

如果一列一列的放置皇后的话，图中黑色位置能放置一个皇后的合法性条件为：
1、绿色线条经过的方格没有皇后 （不处于同一斜线）
2、红色线条经过的方格没有皇后 （不处于同一行）
3、紫色线条经过的方格没有皇后 （不处于同一斜线）

也就是说以一列一列的放置的话，黑色的为起点（0,0）坐标点，紫色和绿色两个线条分别是斜率为1和-1的两个函数，如下图：
紫色线所代表的函数是：y = -x;
绿色先所代表的函数是：y=x;
（横坐标是列，纵坐标为行，注意行从上到下递增）

![](two.png)

凡是位于这两条函数线上的位置（点）以及横坐标（说明位于同一行）都不能有皇后

所以假设某一列皇后的位置用行来记录，比如queen[column] = row,意思是第column列的皇后的位置在第row行。
同行的逻辑很好判断，那么我们想要在黑色方块位置放置一个皇后，怎么判断前面几列是否在绿色线条和紫色线条上已经有了皇后呢？思路也很简单：

假设黑色方块的位置为n列，nRow行，假设位于m列的所在的行是否有皇后位于紫色线或者绿色上，那么就符合下面条件：

~~~java
//假设此时即将在n列放置一个皇后,n>m

//获取m列上皇后所在的行
int mRow = queen[m]
int nRow = queen[n]；
//行的差值
int rowDiff = nRow - mRow;

//列的差值
int columnDiff = n-m;
~~~

这个代码中 rowDiff的绝对值等于columnDiff的绝对值的话那么就说明点位于y=x或者y=-xd 函数上面 

![](three.png)

就说明此时的合适方块的位置是不能在放置皇后了，因为绿色或者紫色上面已经存在皇后了。那么使用代码来判断就是

~~~java
public boolean isLegal(int currentRow,int currentColumn) {
    	//遍历前面几列
    	for(int preColumn=0;preColumn<currentColumn;preColumn++) {
    		int row = queen[preColumn];
    		//说明在子preColumn的低currentRow已经有了皇后
    		if(row==currentRow) {
    			return false;
    		}
    		
    	    //行与行的差值
            int rowDiff= Math.abs(row -currentRow);
          
            //列于列的差值
            int columnDiff =  Math.abs(currentColumn-preColumn);
            //说明斜线上有皇后
            if(rowDiff==columnDiff ){
                return false;
            }
    	}//end for
    	
    	//说明（currentRow,currentColumn)可以摆放。
    	return true;
    }

~~~

这是按照一列一列的方式来进行放置的，所以整体思路就是：在当前列逐步尝试每一行是否可以放置皇后，如果有一个可以放置皇后，就继续查看下一列的每一行是否可以放置皇后

~~~java
 int queen[] = new int[8];
 int count = 0;
    
	private void eightQueen(int currentColumn) {
		//这个for循环的目的是尝试讲皇后放在当前列的每一行
		for(int row=0;row<8;row++) {
			//判断当前列的row行是否能放置皇后
			if(isLegal(row,currentColumn)) {
		        //放置皇后
				queen[currentColumn] = row;
				if(currentColumn!=7) {
					//摆放下一列的皇后
					eightQueen(currentColumn+1);
				
				}else {
					//递归结束，此时row要++了
					count++;
				}
			}
		}//end for
	}
~~~

需要注意的是当currentColumn==7的时候，说明此时已经完成了一种摆放方法，然后for循环继续执行，去尝试其他摆放方法。
测试一波，一共有92种摆放方法：

~~~java
public static void main(String args[]) {
    EightQueen queen = new EightQueen();
    queen.eightQueen(0);
    System.out.println("总共有 " +queen.count+ " 摆放方法");

}

总共有 92 摆放方法
~~~

## 2、约瑟夫环

### 1、问题描述

已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列。依此规律重复下去，直到圆桌周围的人全部出列。

### 2、分析

这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素

### 3、核心实现

1.建立一个具有n个链结点，无头结点的循环链表。

2.确定第1个报数人的位置。

3.不断地从链表中删除链结点，直到链表为空。

~~~java
// 核心代码
while(current!=current.next){
    // 至少还有两个人就仍然kill
    for(int i=1;i<M;i++){
        current=current.next;
    }
    System.out.println(current.next.val+"被kill掉了");
    // 找下一个受害者
    current.next=current.next.next;
}
~~~

### 第二种实现方案

现在假设m=10

0 1 2 3  4 5 6 7 8 9    k=3

第一个人出列后的序列为：

0 1 3 4 5 6 7 8 9

即:

3 4 5 6 7 8 9 0 1（*）

我们把该式转化为:

0 1 2 3 4 5 6 7 8 (**)

则你会发现: （(\**)+3）%10则转化为(\*)式了

也就是说，我们求出9个人中第9次出环的编号，最后进行上面的转换就能得到10个人第10次出环的编号了 

设f(m,k,i)为m个人的环，报数为k，第i个人出环的编号，则f(10,3,10)是我们要的结果

当i=1时，  f(m,k,i) = (m+k-1)%m

当i!=1时，  f(m,k,i)= ( f(m-1,k,i-1)+k )%m

~~~java
// 核心代码
private int ysf(int n,int m,int k){
		if(k==1){
			return (n+m-1)%n+1;
		} else{
	       return (ysf(n-1,m,k-1)+m-1)%n+1;
	    }
	}
~~~

### 第三种方案

数组中每个元素都是一个人，然后对数组进行循环处理，每当数组中的人数到m时，将其标记为淘汰。直到最后数组中只有一个人未被淘汰。

所以，首先，我们需要一个计算方法，参数中有总数和淘汰数两个参数。

~~~java
private void function(int n,int m){}
~~~

第二步，我们需要一个长度为n的布尔值数组，数组的index就表示了第几个人，元素的true和false表示了这个人是否被淘汰。一开始我们需要将所有人都设置为未被淘汰。

~~~java
  boolean[] peopleFlags = new boolean[n];
        for (int i = 0; i < n; i++) {
            peopleFlags[i] = true;
        }
~~~

接下来第三步，我们需要三个变量：

​        第一个变量记录还剩多少人为被淘汰，这个变量的初始值为总人数；

​        第二个变量记录数到了多少，当这个参数等于淘汰数时归零；

​        第三个参数记录当时数到了第几个人，当这个参数等于总人数时归零（因为是一个圈，所以最后一个人数完后又轮到第一个人数数）

~~~java
int peopleLeft = n; //剩下的人数
int count = 0; //计数器，每过一个人加一，加到m时归零
int index = 0; //标记从哪里开始
~~~

第四步就开始循环计算了，首先判断剩余的人数是否大于一，如果大于一进入循环，取index，如果这个人未被淘汰，则计数器加一，如果等于m则淘汰这个人，否则跳过计数继续，当index等于总人数时

~~~java
 int peopleLeft = n; //剩下的人数
        int count = 0; //计数器，每过一个人加一，加到keyNumber时归零
        int index = 0; //标记从哪里开始
        while (peopleLeft > 1) {
            if (peopleFlags[index]) {
                //说明还没有被淘汰 计数器加1
                count++;

                if (count == m) {
                    count = 0; //计数器归0
                    peopleFlags[index] = false; //此人被淘汰
                    peopleLeft--;//未被淘汰的人数-1
                }
            }
            index++;

            //当当前人等于总人数时，则又从第一人开始计数
            if (index == n) {
                index = 0;
            }
        }
~~~

   最后，计算结束后，数组中只有一个元素为true，而这个就是最后没被淘汰的那个人，现在我们就开开始找到是谁赢得了这次比赛。

~~~java
for (int j = 0; j < n; j++) {
            if (peopleFlags[j]) {
         			alive =j+1;
            }
        }
~~~