javascript - 算法:生成小马移动到所有棋盘格的路径

Question

问题描述

我正在尝试获得一种算法，该算法将找到骑士可以在棋盘中移动并访问所有方格而不重复任何方格的可能移动序列的路径。这是可能的，如下图所示

我的方法

为了尝试实现这一目标，我遵循了以下步骤

1. 用 allSquares 创建了一个数组 ['a1', 'a2', 'a3', ..., 'h7', 'h8']
2. 创建了另一个 visitedSquares 数组。初始这是空的 []
3. 为每个方 block 创建了一个包含路径数组的函数。这表示骑士可以从其他方格移动到的方格

{
  "a8": ["c7", "b6"],
  "a7": ["c6", "b5","c8"],
  "a6": ["c5","b4","c7","b8"],

  ...
  "h3": ["f2","g1","f4","g5"],
  "h2": ["f1","f3","g4"],
  "h1": ["f2","g3"]
}

1. 创建了一个 getNextNode() 函数来返回访问节点的最大成本
2. 最后，我尝试通过以下步骤求解最长路径

    while (this.squaresNotVisited.length > 0) {
      const nextTerm = this.getNextNode();
      const currentCost = this.pathCosts[nextTerm[0]];
      const nextPaths: string[] = this.paths[nextTerm[0]];
      nextPaths.forEach(square => {
        if (this.pathCosts[square] < currentCost + 1) {
          this.pathCosts[square] = currentCost + 1;
        }
      });

      this.squaresVisited = [...this.squaresVisited, nextTerm[0]];
      this.squaresNotVisited = this.allSquares.filter(
        x => !this.squaresVisited.includes(x)
      );
    }

下面是完整的Javascript代码

class AppComponent {
  board = {
    columns: ["a", "b", "c", "d", "e", "f", "g", "h"],
    rows: [8, 7, 6, 5, 4, 3, 2, 1]
  };
  allSquares = this.board.columns.reduce(
    (prev, next) => [...prev, ...this.board.rows.map(x => next + x)],
    []
  );

  currentKnightPosition = "h5";
  squaresVisited = [];
  squaresNotVisited = [...this.allSquares];
  nextPossibleKnightPosition = currentKnightPosition => {
    const row = this.board.columns.indexOf(currentKnightPosition[0]);
    const column = Number(currentKnightPosition[1]) - 1;
    return [
      [column - 1, row - 2],
      [column - 1, row + 2],
      [column - 2, row - 1],
      [column - 2, row + 1],
      [column + 1, row - 2],
      [column + 1, row + 2],
      [column + 2, row - 1],
      [column + 2, row + 1]
    ]
      .filter(
        ([row, column]) => column >= 0 && column < 8 && row >= 0 && row < 8
      )
      .map(
        ([row, column]) =>
          this.board.columns[column] + this.board.rows[8 - row - 1]
      );
  };

  paths = this.allSquares.reduce(
    (prev, next) => ({
      ...prev,
      [next]: this.nextPossibleKnightPosition(next)
    }),
    {}
  );

  isNextSquare = square =>
    this.nextPossibleKnightPosition(this.currentKnightPosition).includes(
      square
    );
  costs = { [this.currentKnightPosition]: 0 };
  pathCosts = {
    ...this.allSquares.reduce(
      (prev, next) => ({ ...prev, [next]: -Infinity }),
      {}
    ),
    [this.currentKnightPosition]: 0
  };

  getNextTerm = () => {
    let nonVisted = Object.entries(this.pathCosts).filter(
      ([x, y]) => !this.squaresVisited.includes(x)
    );

    const maxPath = Math.max(...Object.values(nonVisted.map(([, x]) => x)));
    return nonVisted.find(([, x]) => x === maxPath);
  };
  costsCalc = () => {
    while (this.squaresNotVisited.length > 0) {
      const nextTerm = this.getNextTerm();
      const currentCost = this.pathCosts[nextTerm[0]];
      const nextPaths = this.paths[nextTerm[0]];
      nextPaths.forEach(square => {
        if (this.pathCosts[square] < currentCost + 1) {
          this.pathCosts[square] = currentCost + 1;
        }
      });

      this.squaresVisited = [...this.squaresVisited, nextTerm[0]];
      this.squaresNotVisited = this.allSquares.filter(
        x => !this.squaresVisited.includes(x)
      );
    }
  };

  ngOnInit() {
     this.costsCalc();
      console.log(Math.max(...Object.values(this.pathCosts)))
    
  }
}

const app = new AppComponent();
app.ngOnInit()

问题

该方法返回最长路径为 51... 这是不正确的，因为方 block 数为 64。我无法确定错误是在我的代码中还是在我使用的方法中。下面还有一个demo on stackblitz

Answer 1

你的函数卡住了

在每一步中，您的方法只采用最长的路径并更新其所有邻居。这不是撤消决策，这就是它卡在 52 路径长度的原因。

当您发现当前的解决方案不起作用时，请务必返回，即 Backtracking .

可能的实现

...使用 Warnsdorff's rule .

const findPath = (knightPosition) => {
  if (squaresVisited.size === allSquares.length - 1) return [knightPosition]

  squaresVisited.add(knightPosition)
  const neighbors = paths[knightPosition]
    .filter(neighbor => !squaresVisited.has(neighbor))
    .map(neighbor => {
      const neighborCount = paths[neighbor]
        .filter(square => !squaresVisited.has(square))
        .length
      return {
        position: neighbor,
        count: neighborCount
      }
    })
  const minNeighborsCount = Math.min(...neighbors.map(({ count }) => count))
  const minNeighbors = neighbors.filter(neighbor => neighbor.count === minNeighborsCount)
  for (const minNeighbor of minNeighbors) {
    const { position, count } = minNeighbor
    const path = findPath(position)
    if (path) return [knightPosition, ...path]
  }
  squaresVisited.delete(knightPosition)
}

完整的工作示例

const board = {
  columns: ["a", "b", "c", "d", "e", "f", "g", "h"],
  rows: [8, 7, 6, 5, 4, 3, 2, 1]
};

const allSquares = board.columns.reduce(
  (prev, next) => [...prev, ...board.rows.map(x => next + x)],
  []
);

const nextPossibleKnightPositions = currentKnightPosition => {
  const row = board.columns.indexOf(currentKnightPosition[0]);
  const column = Number(currentKnightPosition[1]) - 1;
  return [
    [column - 1, row - 2],
    [column - 1, row + 2],
    [column - 2, row - 1],
    [column - 2, row + 1],
    [column + 1, row - 2],
    [column + 1, row + 2],
    [column + 2, row - 1],
    [column + 2, row + 1]
  ]
    .filter(
      ([row, column]) => column >= 0 && column < 8 && row >= 0 && row < 8
    )
    .map(
      ([row, column]) =>
        board.columns[column] + board.rows[8 - row - 1]
    );
};

const paths = allSquares.reduce(
  (prev, next) => ({
    ...prev,
    [next]: nextPossibleKnightPositions(next)
  }),
  {}
);

const squaresVisited = new Set();

const findPath = (knightPosition) => {
  if (squaresVisited.size === allSquares.length - 1) return [knightPosition]

  squaresVisited.add(knightPosition)
  const neighbors = paths[knightPosition]
    .filter(neighbor => !squaresVisited.has(neighbor))
    .map(neighbor => {
      const neighborCount = paths[neighbor]
        .filter(square => !squaresVisited.has(square))
        .length
      return {
        position: neighbor,
        count: neighborCount
      }
    })
  const minNeighborsCount = Math.min(...neighbors.map(({ count }) => count))
  const minNeighbors = neighbors.filter(neighbor => neighbor.count === minNeighborsCount)
  for (const minNeighbor of minNeighbors) {
    const { position, count } = minNeighbor
    const path = findPath(position)
    if (path) return [knightPosition, ...path]
  }
  squaresVisited.delete(knightPosition)
}

const path = findPath("h5");
console.log(path)

allSquares.forEach(square => {
  squaresVisited.clear()
  const path = findPath(square)
  if(path.length !== 64) throw new Error(sqaure)
})
console.log("Works for all squares")