什么是回溯法？

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

用回溯算法解决问题的一般步骤：

1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。

2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。

3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

基本思想

从一条路往前走，能进则进，不能进则退回来，换一条路再试。

能解决哪些问题？

• 排列、组合（子集、幂集、字符全排列）。

• 二维数组下的DFS搜索（黄金矿工、数独、装载问题、0-1背包问题、旅行售货员问题、八皇后问题、迷宫问题、图的m着色问题）

• 数组、字符串，给定一个特定的规则，尝试搜索迭代找到某个解。

回溯的解空间

回溯算法有两种常见的解空间模型，分别对应数学中的两种暴力思想，组合以及排列。其中子集问题，对应数学中的组合问题。排列问题对应数学中的排列问题。

解数独

数独，是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”

利用回溯算法解数独。思路如下：

1，从0行0列开始，依次往里面填入1-9的数字；

2，然后判断填入这个数字后，该数字对应的行，列和九宫格是否满足不重复的条件；

3，如果当前填入的数字满足，就继续填入下一个数字，下一个数字又从1-9中尝试，如果有满足的数字就说明该数字可用，如果没有，则将该数字又重新置为空格，如此循环往复；

4，如果将所有的数字都尝试了还是没有合适的额，那说明本问题无解，返回false；

/**java 递归*/
public class ShuduPro {private int[][] sudoku;public ShuduPro(int[][] sudoku) {this.sudoku = sudoku;}public static void main(String[] args) {int[][] sudoku={{7, 0, 0, 0, 0, 0, 0, 0, 9},{1, 4, 0, 3, 0, 9, 0, 0, 6},{0, 0, 0, 0, 0, 0, 5, 1, 0},{0, 0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 2, 0, 8, 1, 0, 0, 0},{0, 0, 9, 0, 2, 0, 8, 0, 0},{0, 0, 0, 0, 0, 0, 0, 0, 0},{0, 2, 8, 5, 0, 6, 9, 0, 0},{0, 0, 0, 1, 0, 0, 3, 0, 2}};ShuduPro sudu = new ShuduPro(sudoku);sudu.backTrace(0,0);}private void backTrace(int i, int j) {//完成，打印数组if(i==8 && j==9){print_sudoku();return;}//判断是否到列尾，到列尾没到行尾，就换行if(j == 9){i++;j=0;}//如果是空格就填值if (sudoku[i][j] == 0){for (int n = 1; n <=9; n++){//判断空格中填任一个数是否符合规则if(check_repeat(i,j,n)){/**赋值* 进入下一个空格* 初始化该空格*/sudoku[i][j] = n;backTrace(i,j+1);sudoku[i][j]=0;}}}else{backTrace(i,j+1);}}/**** @param row   行号* @param col   列号* @param temp   赋的值* @return*/private boolean check_repeat(int row, int col, int temp) {//判断所在行和列是否有重复数字for (int i=0; i < 9; i++){if(sudoku[row][i] == temp || sudoku[i][col] == temp){return false;}}//判断所在小九宫格中是否有重复int tempRow = (row / 3) * 3;int tempCol = (col / 3) * 3;for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){if(sudoku[tempRow + i][tempCol + j] == temp){return false;}}}return true;}//打印矩阵private void print_sudoku() {for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++){System.out.print(sudoku[i][j]+" ");}System.out.println(" ");}System.out.println(" ");}}

数独结果：