We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. KnightL on a Chessboard
  5. Discussions

KnightL on a Chessboard

Sort 109 Discussions, By:

  • ROCKET_RONALDO
     + 4 comments

    very bad explanation of the sample test case

  • sizzlingsnigz271
     + 3 comments

    BFS works like a charm here because in unweighted graphs BFS guarantees that the first time you visit a cell it gives the shortest path.

  • dhawal_1304
     + 1 comment

    Can somebody explain the problem.For 5X5 chess board how the result is :

    4 4 2 8 4 2 4 4 2 4 -1 -1 8 4 -1 1

    I did not get anything out of the explanation.

  • mannuiitr
     + 0 comments

    bad explaination ...

  • btdiehr
     + 5 comments

    Python 3 solution.

    A couple things to note: - The number of moves funciton is symetteric, so I went ahead and memoized it which will half our run time (don't think this is necessary but a good thing to recognize) - I notice a lot of people are using long if statements to get the adjacent list of positions. I felt a simple filter lambda was cleaner.

    memo = [[]]

def adj(a, b, x, y, n):
    return filter(lambda v : v[0] >= 0 
      and v[1] >= 0 
      and v[0] < n 
      and v[1] < n,
      [
        [x + a, y + b],
        [x + a, y - b],
        [x - a, y + b],
        [x - a, y - b],
        [x + b, y + a],
        [x + b, y - a],
        [x - b, y + a],
        [x - b, y - a],
    ])

def move(a, b, n):
    global memo
    # Since move(a, b, n) == move(b, a, n),
    # we take advantage of this symmtery by memoization.
    if memo[a][b] is not None:
        return memo[a][b]
    visited = [[False] * n for _ in range(n)]
    # Queue stores elements as [x, y, depth]
    # Start with top left position
    queue = [[0, 0, 0]]
    while len(queue) > 0:
        x, y, l = queue.pop()
        # At the end, return level of node
        if x == n - 1 and y == n - 1:
            memo[a][b] = l
            memo[b][a] = l
            return l
        neighbors = [
            [x_i, y_i]
            for x_i, y_i in adj(a, b, x, y, n) 
            if visited[y_i][x_i] == False
        ]
        
        for x_i, y_i in neighbors:
            visited[y_i][x_i] = True 
            queue.insert(0, [x_i, y_i, l + 1])
            
    memo[a][b] = -1 
    memo[b][a] = -1 
    return -1 
    

# Complete the knightlOnAChessboard function below.
def knightlOnAChessboard(n):
    global memo
    memo = [[None for _ in range(n + 1)] for _ in range(n + 1)]
    results = []
    for a in range(1, n):
        results.append([])
        for b in range(1, n):
            results[a - 1].append(move(a, b, n))
    return results
Load more conversations