Ways to place K bishops on an NÃ — N chessboard so that no two attack | CPP implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int squares ( int i ) { if ( ( i & 1 ) == 1 ) return i / 4 * 2 + 1 ; else return ( i - 1 ) / 4 * 2 + 2 ; } long bishop_placements ( int n , int k ) { if ( k > 2 * n - 1 ) return 0 ; long dp [ n * 2 ] [ k + 1 ] ; for ( int i = 0 ; i < n * 2 ; i ++ ) { for ( int j = 0 ; j < k + 1 ; j ++ ) { dp [ i ] [ j ] = 0 ; } } for ( int i = 0 ; i < n * 2 ; i ++ ) dp [ i ] [ 0 ] = 1 ; dp [ 1 ] [ 1 ] = 1 ; for ( int i = 2 ; i < n * 2 ; i ++ ) { for ( int j = 1 ; j <= k ; j ++ ) { dp [ i ] [ j ] = dp [ i - 2 ] [ j ] + dp [ i - 2 ] [ j - 1 ] * ( squares ( i ) - j + 1 ) ; } } long ans = 0 ; for ( int i = 0 ; i <= k ; i ++ ) { ans += dp [ n * 2 - 1 ] [ i ] * dp [ n * 2 - 2 ] [ k - i ] ; } return ans ; } int main ( ) { int n = 2 ; int k = 2 ; long ans = bishop_placements ( n , k ) ; cout << ( ans ) ; }