Ways to place K bishops on an NÃ — N chessboard so that no two attack | returns the number of squares in diagonal i ; returns the number of ways to fill a n * n chessboard with k bishops so that no two bishops attack each other . ; return 0 if the number of valid places to be filled is less than the number of bishops ; dp table to store the values ; Setting the base conditions ; calculate the required number of ways ; stores the answer ; Driver code
def squares ( i ) : NEW_LINE INDENT if ( ( i & 1 ) == 1 ) : NEW_LINE INDENT return int ( i / 4 ) * 2 + 1 NEW_LINE DEDENT else : NEW_LINE INDENT return int ( ( i - 1 ) / 4 ) * 2 + 2 NEW_LINE DEDENT DEDENT def bishop_placements ( n , k ) : NEW_LINE INDENT if ( k > 2 * n - 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT dp = [ [ 0 for i in range ( k + 1 ) ] for i in range ( n * 2 ) ] NEW_LINE for i in range ( n * 2 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 1 NEW_LINE DEDENT dp [ 1 ] [ 1 ] = 1 NEW_LINE for i in range ( 2 , n * 2 , 1 ) : NEW_LINE INDENT for j in range ( 1 , k + 1 , 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = ( dp [ i - 2 ] [ j ] + dp [ i - 2 ] [ j - 1 ] * ( squares ( i ) - j + 1 ) ) NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 0 , k + 1 , 1 ) : NEW_LINE INDENT ans += ( dp [ n * 2 - 1 ] [ i ] * dp [ n * 2 - 2 ] [ k - i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 2 NEW_LINE k = 2 NEW_LINE ans = bishop_placements ( n , k ) NEW_LINE print ( ans ) NEW_LINE DEDENT