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
< ? php function squares ( $ i ) { if ( ( $ i & 1 ) == 1 ) return intval ( $ i / 4 ) * 2 + 1 ; else return intval ( ( $ i - 1 ) / 4 ) * 2 + 2 ; } function bishop_placements ( $ n , $ k ) { if ( $ k > 2 * $ n - 1 ) return 0 ; $ dp = array_fill ( 0 , $ n * 2 , array_fill ( 0 , $ k + 1 , NULL ) ) ; for ( $ i = 0 ; $ i < $ n * 2 ; $ i ++ ) $ dp [ $ i ] [ 0 ] = 1 ; $ dp [ 1 ] [ 1 ] = 1 ; for ( $ i = 2 ; $ i < $ n * 2 ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ k ; $ j ++ ) $ dp [ $ i ] [ $ j ] = $ dp [ $ i - 2 ] [ $ j ] + $ dp [ $ i - 2 ] [ $ j - 1 ] * ( squares ( $ i ) - $ j + 1 ) ; } $ ans = 0 ; for ( $ i = 0 ; $ i <= $ k ; $ i ++ ) { $ ans += $ dp [ $ n * 2 - 1 ] [ $ i ] * $ dp [ $ n * 2 - 2 ] [ $ k - $ i ] ; } return $ ans ; } $ n = 2 ; $ k = 2 ; $ ans = bishop_placements ( $ n , $ k ) ; echo $ ans ; ? >