Knight walk backtracking solution issue

Question

I have a doubt on the backtracking solution I wrote for below problem:

Given a square chessboard of N x N size, the position of Knight and the position of a target are given. We need to find out the minimum steps a Knight will take to reach the target position

My back tracking solution is :

    #knight walk problem
 #knight walk problem
#cx---crnt x value
#cy---crnt y value
#Dx---destintion X value
#Dy----destintion Y value
#count---count of steps


def kingnight(Cx,Cy,Dx,Dy,outboard,steps):
  if Cx==Dx and Cy==Dy:
    outboard[Cx][Cy]=1
    return steps
  if Cx<0 or Cy<0 or Cx>=len(outboard) or Cy>=len(outboard) or outboard[Cx][Cy]==1:
    return float('inf')
  outboard[Cx][Cy]=1
  min1=kingnight(Cx+2,Cy-1,Dx,Dy,outboard,steps+1)
  min2=kingnight(Cx+2,Cy+1,Dx,Dy,outboard,steps+1)
  min3=kingnight(Cx-2,Cy+1,Dx,Dy,outboard,steps+1)
  min4=kingnight(Cx-2,Cy-1,Dx,Dy,outboard,steps+1)
  min5=kingnight(Cx+1,Cy+2,Dx,Dy,outboard,steps+1)
  min6=kingnight(Cx+1,Cy-2,Dx,Dy,outboard,steps+1)
  min7=kingnight(Cx-1,Cy+2,Dx,Dy,outboard,steps+1)
  min8=kingnight(Cx-1,Cy-2,Dx,Dy,outboard,steps+1)
  crntmin=min(min1,min2,min3,min4,min5,min6,min7,min8)
  outboard[Cx][Cy]=0 #backtracking
  return crntmin

When I call the function:

n=4
board=[[0 for _ in range(n)] for i in range(n)]
kingnight(1,1,0,0,board,0)

It shows the expected output. But when I call with the below:

n=6
board=[[0 for _ in range(n)] for i in range(n)]
kingnight(2,3,5,5,board,0)

It should return 3 but is an infinite loop.

Where I am wrong?

Answer 1

The problem is that your algorithm is looking for every possible path that the knight can take from the starting position. On larger boards this number of paths grows exponentially. Your loop is not infinite; it just needs to check too many paths.

If we simplify a bit and assume that the knight on a 6x6 board can take on average 4 moves, and that paths are on average 20 steps long, then we have 4²⁰ paths, i.e. 1e+12 paths. This is an underestimation.

How to solve

This brute force algorithm is not good enough.

Use a breadth-first search instead of a depth-first search and log on each visited board cell the (shortest) distance from the source (which also serves as a visited-marker). Unvisited fields should be initialised with -1. The source will get 0, ...etc.

That will be the main improvement you need. You can also apply some heuristics, and turn it into an A* algorithm, where the estimated steps to the target should be an underestimation, so for instance the taxicab distance divided by 3.

Implementation

I went for an implementation where you don't pass the board to the function, but just n, and the function returns a path of coordinates.

The function will then create its board locally and fill it during the breadth-first with values that represent the position where the knight came from on its optimal path (to that square).

Here is the code:

def kingnight(cx,cy,dx,dy,n):
    board=[[0 for _ in range(n)] for i in range(n)]
    q = [(cx, cy)]
    board[cx][cy] = (-1, -1)
    while q:
        frontier = []
        for cx, cy in q:
            for mx, my in ((-2,-1),(-1,-2),(1,-2),(2,-1),(1,2),(2,1),(-2,1),(-1,2)):
                tx = cx + mx
                ty = cy + my
                if 0 <= tx < n and 0 <= ty < n and not board[tx][ty]:
                    board[tx][ty] = (cx, cy)
                    if tx == dx and ty == dy:
                        # build path
                        path = []
                        while tx >= 0:
                            path.append((tx, ty))
                            tx, ty = board[tx][ty]
                        return path[::-1]
                    frontier.append((tx, ty))
        q = frontier
    return  # Not possible

# Demo
n=6
print(kingnight(2,3,5,5,n))