Блог пользователя sauban

Longest Chess Knight Path Problem
Автор sauban, история, 6 лет назад, По-английски

So I came across this problem, and I could not solve it. Can I have some hints?

Given a n x m chess board, a starting position (r1, c1) and a target position (r2, c2), you have to output the maximum number of moves a chess knight can make to get to the target position. Each cell can only be visited once.

n and m were ~400.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

If the problem is given as above, the maximum number of moves is infinite: make one move and come back to an initial position. The only exception is when your chess board is so small that the only possible move is to (r2, c2).

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I am sorry mate, I had this in mind but forgot to add it in the post. It was written explicitly in the problem statement that each cell can only be visited once. I will update my post. Thanks.

    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by sauban (previous revision, new revision, compare).

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

BUMP

→ Ответить
»
6 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

A depth-first search solution for this problem may be implemented as follows. Consider the chess-board as an n × m array of cells. In each cell, store the present longest path from the source position, a boolean flag that indicates whether or not the cell has been visited, and a list of cell to which the knight can move to when placed at this cell. Initialize the longest path in the source position to zero, and in all other cells to minus infinity. Starting from the source position, the recursive depth-first search should move the knight to a new cell if it has not been visited and if the longest path of the new cell is less than the present longest path+1. The longest path of the cell should be updated upon visiting it. The boolean flag should be set to true upon visiting the cell, and should be set to false before returning from the recursive depth-first search function. After completing the depth-first search, the solution of the problem should be the value of the longest path stored in the destination position.

P.S. You may check the Knight's tour wiki page for related information.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have thought about the DFS solution, but it will take exponential time in worst case (saying this from top of my head, correct me if I am wrong).

    I checked the Knight's tour wiki page and couldn't get any leads.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 21   Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, this can happen in general when depth-first search tree is traversed exhaustively. Restricting the number of visits to each cell to at most one should not only imply that the maximum path length (number of moves) can never exceed n × m - 1 when the starting position and the target position are different, but should also imply that the search tree is pruned as the knight makes more moves on the chess board, as the maximum number of possible cells which can be still part of the rest of the knight maximum path decreases by one each time the knight makes a new move. By definition, the knight can make at most 8 different moves from its present cell, and the maximum number of moves at each cell for the knight depends on the cell position and the chess board dimensions. The following is an example for the standard 8 × 8 chess board. 

      2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

      The actual number of possible moves next to the present cell should be less than or equal to the specified number when some of all possible next cells were visited before reaching the present cell.

      The following references about the knight's tour problem may provide helpful hints about your problem.

      1. An efficient algorithm for the Knight’s tour problem

      2. Knight’s Tour Problem and its Graph Analysis

      → Ответить