Algorithm: Generate path for a Knight move to all Chess Board Squares

Question

Problem description

I am trying to get an algorithm that will find the path of a possible sequence of moves that a Knight can move in a chessboard and visit all squares without repeating any of the squares. This is possible as illustrated by the diagram below

My Approach

To try and achieve this I have followed the below steps

Created an array with allSquares ['a1', 'a2', 'a3', ..., 'h7', 'h8']
Created another array of visitedSquares. initialy this is empty []
Created a function an array of paths for each square. This represents squares to which a Knight can move from other squares

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

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

Created a getNextNode() function to return the maximum of the cost of nodes visited
Finally I try to solve for the longest path with the below steps

    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)
      );
    }

Below is the complete Javascript code

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()

The Problem

The Approach returns that the longest path is 51... which is incorrect as the number of squares are 64. I am stuck at whether the error is in my code or the error is in the approach I am using. Below is also a demo on stackblitz

user_5312432 · Answer

You're function gets stuck

In each step your method just takes the longest path and updates all its neighbors. It's not undoing decisions, that's why it gets stuck at a path length of 52.

It is essential that you go back, when you find out your current solution does not work, i.e. Backtracking.

Possible implementation

...using 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)
}

Full working example

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")