Minimum moves of a knight with bishop

Question

The question is minimum moves of a knight from point A to B in an n*n chessboard(knights can move two steps in the horizontal direction and one step in the vertical direction or two in vertical one in horizontal). There is a bishop on the chess board that travels diagonally and the knight cannot travel to positions threatened by the bishop unless the bishop is dead or the position is point B. The knight can choose to kill the bishop (if it is in a position that it can travel to) and free all the previously threatened positions.

I got this question in an online assessment that I took, but only got 10 out of 15 test cases correct. I figured I might need to add a boolean value to the tuples in the queue of whether the bishop is alive in the latest step but it was too late.

How can I modify this?

from collections import deque
import math

n = 5
startRow = 0
startCol = 0
endRow = 4
endCol = 3
bishopRow = 3
bishopCol = 0
from collections import deque
import math
#
# Complete the 'moves' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. INTEGER startRow
#  3. INTEGER startCol
#  4. INTEGER endRow
#  5. INTEGER endCol
#  6. INTEGER bishopRow
#  7. INTEGER bishopCol
#
def isBishopAlive(n, bishopRow, bishopCol):
    if bishopRow < n and bishopCol < n:
        return True
    else:
        return False
def moves(n, startRow, startCol, endRow, endCol, bishopRow, bishopCol):
    # Write your code here
    x, y = abs(endRow), abs(endCol)
    res = 0
    moves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1))
    visited = []
    queue = deque()
    queue.append((startRow, startCol, 0))
    while queue:
        i, j, steps = queue.popleft()
        if i == x and j == y:
            return res + steps
        for di, dj in moves:
            cr = i + di
            cc = j + dj
            if isBishopAlive(n, bishopRow, bishopCol) == True:
                if abs(cr-bishopRow) == abs(cc-bishopCol):
                    if cc != y and cr != x:
                        continue
                if (cr == bishopRow) and (cc == bishopCol):
                    bishopRow, bishopCol = math.inf, math.inf
            if abs(cr) > n-1 or abs(cc) > n-1:
                continue
            if (cr, cc) in visited:
                continue
            if isBishopAlive(n, bishopRow, bishopCol) == True:
                bishop = True
            else:
                bishop = False
            if ((x-i) * di) > 0 or ((y-j) * dj) > 0:
                queue.append([cr, cc, steps+1])
                visited.append((cr, cc))
    return -1

user_5459839 · Answer

There are the following issues in your code:

The bishop can never be captured, because when that square is reached with cr and cc, then first the if abs(cr-bishopRow) == abs(cc-bishopCol) condition will be evaluated -- and found true -- followed by a continue.
When the bishop would have been captured, your code never puts it back when looking at other paths that did not capture the bishop. Instead, the items on the queue should include whether or not that state was achieved by capturing the bishop or not.
Items in the visited list do not indicate whether the visit happened when the bishop was still alive or not. Yet this is important, because if you visited a square first with the bishop still alive, but then visit it again when the bishop is captured, that second visit could lead to a better solution. So include the alive-status in the tuples when marking a square as visited.
The code allows negative coordinates for cr or cc to be pushed unto the queue. This should be avoided.

This exclusion of moves that move away from the target is too optimistic:

if ((x-i) * di) > 0 or ((y-j) * dj) > 0

Take for instance this board, where "N" is the knight, "B" the bishop and "e" the end square:

┌───┬───┬───┬───┬───┐
│   │   │   │   │   │
├───┼───┼───┼───┼───┤
│   │   │   │   │ B │
├───┼───┼───┼───┼───┤
│   │   │ N │   │   │
├───┼───┼───┼───┼───┤
│   │   │   │   │   │
├───┼───┼───┼───┼───┤
│   │   │   │   │ e │
└───┴───┴───┴───┴───┘

The bishop must be taken on the first move, and then the knight must move away to the top row for the optimal solution.

I would suggest to just remove this condition or else make sure it is not too strict and will never exclude an optimal path.

Not a problem, but:

res is never assigned another value than 0: this variable is not needed
bishop is only set, but never read: this variable (and the if...else block around it) is not needed
visited should better be a set than a list, so to have a better time complexity.
endRow and endCol will never be negative, so it is not useful to copy their absolute values in x and y. Just use the original parameter variables.
As you mark squares as visited at the moment you put them on the queue, you should also do the same with the start square before entering the loop.
There is a nested if that leads to a continue. These if conditions can be combined into one if condition using and
Two if conditions at the same level that both lead to continue can be combined into one if condition using or
The parentheses around (cr == bishopRow) are not necessary.
You could save some execution time by checking the target was reached when performing a move, instead of waiting until that move is popped from the queue. This just means you have to have an initial check to see whether the starting position is equal to the end position, but it is worth it.

Here is a corrected version:

def moves(n, startRow, startCol, endRow, endCol, bishopRow, bishopCol):
    if startRow == endRow and startCol == endCol:  # Deal with trivial case
        return 0
    moves = ((2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1))
    queue = deque()
    queue.append((startRow, startCol, True, 0))  # Include that bishop is alive
    # Let visited be a set. Mark start as visited and include alive-status
    visited = set([(startRow, startCol, True)])
    while queue:
        i, j, alive, steps = queue.popleft()
        for di, dj in moves:
            cr = i + di
            cc = j + dj
            if cr == endRow and cc == endCol:  # When found, don't bother about queuing it
                return steps + 1 # No need for a res variable 
            # Update alive-state, just for current path
            stillalive = alive and (cr != bishopRow or cc != bishopCol)
            # Neither cr/cc should be negative
            if 0 <= cr < n and 0 <= cc < n and (cr, cc, stillalive) not in visited and (
                    not stillalive or abs(cr - bishopRow) != abs(cc - bishopCol)):
                queue.append((cr, cc, stillalive, steps + 1))  # Append alive-status too
                visited.add((cr, cc, stillalive))  # Visited should depend on alive
    return -1

Minimum moves of a knight with bishop

1 Answers