回溯算法

---

  回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法说白了就是穷举法。
  回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯点。许多复杂的，规模较大的问题都可以使用回溯法，有通用解题方法的美称。

一般步骤

• 针对所有问题，定义问题的解空间，它至少包含问题的一个最优解。
• 确定易于搜索的解空间结构，使得能用回溯法方便的搜索整个解空间。
• 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

题目1 N皇后问题leetCode51 (opens new window)

在 N×N 格的国际象棋上摆放 N 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

思路

• 从每一行开始，向上一行递归查询每一列是否符合皇后的摆放位置。
  • 上n-1行同一列不能放
  • 上n-1行m-1列不能放
  • 上n-1行m+1列不能放
• 对角线判断

/**
 * @param {number} n
 * @return {string[][]}
 */
function solveNQueens(n) {
    let result = new Array(n);
    let results = [];//用于存放皇后的列位置
    //深度优先遍历
    //row 行 column列
    const dfs = (row,column) => {
        let leftColumn =  column-1;
        let rightColumn = column+1;
        for(let i = row - 1;i >= 0;i--){
            if(result[i] == column){
                return false;
            }
            if(leftColumn >= 0 && result[i] == leftColumn){
                return false;
            }
            if(rightColumn < n && result[i] == rightColumn){
                return false;
            }
            leftColumn--;
            rightColumn++;
        }
        return true;
    }
    const createQueens = (row) => {
        if(row == n){
            results.push(result.map(c=>'.'.repeat(c)+'Q'+'.'.repeat(n-1-c)));
            return;
        }
        //n表示列
        for(let j = 0;j < n;j++){
            if(dfs(row,j)){
                result[row] = j;
                createQueens(++row)
            }
        }
    }
    createQueens(0);
    return results;
};