回溯是一种渐进式寻找并构建问题解决方式的策略。我们从一个可能的动作开始并试着用这个动作解决问题。如果不能解决,就回溯并选择另-个动作直到将问题解决。根据这种行为，回溯算法会尝试所有可能的动作(如果更快找到了解决办法就尝试较少的次数)来解决问题。

有一些可用回溯解决的著名问题:

  • 骑士巡逻问题.
  • N皇后问题
  • 迷宫老鼠问题
  • 数独解题器

骑士周游问题

image.png
image.png

image.png

  1. console.log(run(3, 4, 0, 0))
  3. // X、Y表示棋盘X轴、Y轴大小 ，x、y 表示马儿起始位置所在X、Y轴的坐标
  4. function run (X, Y, x, y) {
  5.   // 标记马儿所有走的路径
  6.   const visited = Array.from({length: X * Y}, () => false)
  8.   let finished = false // 标记马儿是否走完所有方格
  9.   const chessBoard = new Array(Y) // 创建一个棋盘
  10.   for(let i = 0; i < chessBoard.length; i++){
  11.     chessBoard[i] = Array.from({length: X}, () => 0)
  12.   }
  13.   return traversalChessBoard(chessBoard, x, y)
  15.   // chessBoard [][] 棋盘  x, y起始位置， step走了多少步，step等于棋盘大小时即成功走完所有棋盘
  16.   function traversalChessBoard(chessBoard, x, y, step = 1) {
  17.     chessBoard[x][y] = step // 标记棋盘走了一步
  18.     visited[x * X + y] = true
  19.     const nextSteps = next({y, x}, X, Y) // 下一步马儿能走哪些点
  20.     // 这里体现了贪心算法
  21.     nextSteps.sort((p1, p2) => next(p1, X, Y).length - next(p2, X, Y).length)
  22.     while (nextSteps.length) {
  23.       const p = nextSteps.shift()
  24.       if(!visited[p.x * X + p.y]) {
  25.         traversalChessBoard(chessBoard, p.x, p.y, step + 1)
  26.       }
  27.     }
  28.     if (step < X * Y) {
  29.       if (!finished) { // 只能走这么多步，没能走完，只好回退了， 这里体现了回溯算法
  30.         chessBoard[x][y] = 0
  31.         visited[x * X + y] = false
  32.       }
  33.     } else {
  34.       finished = true
  35.     }
  36.     return chessBoard
  37.   }
  38. }
  40. function next(currPoint, X, Y) {
  41.   const nextSteps = []
  42.   let y, x
  43.   // 0
  44.   if ((y = currPoint.y + 2) < X && (x = currPoint.x - 1) >= 0 ) {
  45.     nextSteps.push({y, x})
  46.   }
  47.   // 1
  48.   if ((y = currPoint.y + 2) < X && (x = currPoint.x + 1) < Y) {
  49.     nextSteps.push({y, x})
  50.   }
  51.   // 2
  52.   if ((y = currPoint.y + 1) < X && (x = currPoint.x + 2)  < Y ) {
  53.     nextSteps.push({y, x})
  54.   }
  55.   // 3
  56.   if ((y = currPoint.y - 1) >= 0 && (x = currPoint.x + 2)  < Y ) {
  57.     nextSteps.push({y, x})
  58.   }
  59.   // 4
  60.   if ((y = currPoint.y - 2) >= 0 && (x = currPoint.x + 1) < Y ) {
  61.     nextSteps.push({y, x})
  62.   }
  63.   // 5
  64.   if ((y = currPoint.y - 2) >= 0 && (x = currPoint.x - 1) >= 0 ) {
  65.     nextSteps.push({y, x})
  66.   }
  67.   // 6
  68.   if ((y = currPoint.y - 1) >= 0 && (x = currPoint.x - 2) >= 0 ) {
  69.     nextSteps.push({y, x})
  70.   }
  71.   // 7
  72.   if ((y = currPoint.y + 1) < X && (x = currPoint.x - 2) >= 0 ) {
  73.     nextSteps.push({y, x})
  74.   }
  75.   return nextSteps
  76. }

老鼠迷宫

只能走简单的迷宫

  1. console.log(ratInAMaze([
  2.   [1, 0, 0, 0],
  3.   [1, 1, 1, 1],
  4.   [0, 0, 1, 0],
  5.   [0, 1, 1, 1]
  6. ]))
  8. function ratInAMaze(maze) {
  9.   const solution = [];
  10.   for (let i = 0; i < maze.length; i++) {
  11.     solution[i] = [];
  12.     for (let j = 0; j < maze[i].length; j++) {
  13.       solution[i][j] = 0;
  14.     }
  15.   }
  16.   if (findPath(maze, 0, 0, solution) === true) {
  17.     return solution;
  18.   }
  19.   return 'NO PATH FOUND';
  20. }
  22. function findPath(maze, x, y, solution) {
  23.   const n = maze.length;
  24.   if (x === n - 1 && y === n - 1) {
  25.     solution[x][y] = 1;
  26.     return true;
  27.   }
  28.   if (isSafe(maze, x, y) === true) {
  29.     solution[x][y] = 1;
  30.     if (findPath(maze, x + 1, y, solution)) {
  31.       return true;
  32.     }
  33.     if (findPath(maze, x, y + 1, solution)) {
  34.       return true;
  35.     }
  36.     solution[x][y] = 0;
  37.     return false;
  38.   }
  39.   return false;
  40. }
  42. function isSafe(maze, x, y) {
  43.   const n = maze.length;
  44.   if (x >= 0 && y >= 0 && x < n && y < n && maze[x][y] !== 0) {
  45.     return true;
  46.   }
  47.   return false;
  48. }

复原ip

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 ‘.’ 分隔。

  1. function run (str) {
  2.     const list = []
  3.   figureItOut(str, [])
  4.   return list
  5.   function figureItOut (str, arr) {
  6.     if (!str.length && arr.length == 4) {
  7.       list.push(arr.join('.'))
  8.       return
  9.     }
  10.     if (arr.length == 4 ) {
  11.       return
  12.     }
  13.     let tp = '', tps = str.split('')
  14.     for (let i = 1; i <= 3; i++) {
  15.       tp = tps.pop() + tp
  16.       if (legal(tp)) {
  17.         let tpa = arr.slice()
  18.         tpa.unshift(tp)
  19.         figureItOut(tps.join(''), tpa)
  20.       }
  21.     }
  22.   }
  23.   function legal(num) {
  24.     if (Number(num) < 256 && Number(num).toString() == num) {
  25.         return true
  26.     }
  27.     return false
  28.     }
  29. }
  30. console.log(run('25525511135'))