labuladong的算法小抄之js实现-第0章-回溯算法

文章直达地址: https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban

本系列为labuladong的算法小抄的javascript实现版本，实现原理参考labuladong的算法小抄。本文为第0章第3小节《回溯算法》所涉及的代码，直接上代码：

// //全排列
// const result = [];

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const result = [];
  const tracks = [];
  backtrack(nums, tracks);
  function backtrack(nums, tracks) {
    if (tracks.length == nums.length) {
      result.push(Array.from(tracks));
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (tracks.indexOf(nums[i]) >= 0) continue;
      tracks.push(nums[i]);
      backtrack(nums, tracks);
      tracks.pop();
    }
  }

  return result;
};

// permute([1, 2, 3]);
// console.log(result);

// n皇后问题
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  var result = [];
  var chessboard = new Array(n);
  chessboard.fill(new Array(n + 1).join("."));

  backtrack(chessboard, 0);

  function replaceStr1(str, index, char) {
    const strAry = str.split("");
    strAry[index] = char;
    return strAry.join("");
  }
  function backtrack(chessboard, row) {
    if (row === n) {
      result.push(JSON.parse(JSON.stringify(chessboard)));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (!isValid(chessboard, row, col)) {
        continue;
      }
      chessboard[row] = replaceStr1(chessboard[row], col, "Q");
      backtrack(chessboard, row + 1);
      chessboard[row] = replaceStr1(chessboard[row], col, ".");
    }
  }
  function isValid(chessboard, row, col) {
    // col测试
    for (let i = 0; i < row; i++) {
      if (chessboard[i][col] == "Q") return false;
    }

    // 左上角
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (chessboard[i][j] == "Q") return false;
    }

    // 右上角
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (chessboard[i][j] == "Q") return false;
    }
    return true;
  }
  return result;
};

solveNQueens(4);