Data Modelling & AI Data Structure & Algorithm

Count pair of bishops that will attack each other on a N x N chessboard

23 June 2025

0

Given a N x N chessboard and the position of X bishops on it, the task is to calculate the count of pairs of bishops such that they attack each other. Note that while considering a pair of bishops, all the other bishops are not considered to be on the board.

Example:

Input: N = 5, bishops[][] = {{2, 1}, {3, 2}, {2, 3}}
Output: 2
Explanation: The bishops on the positions {2, 1} and {3, 2} and bishops on the positions {3, 2} and {2, 3} attack each other.

Input: N = 10, bishops[][] = {{1, 1}, {1, 5}, {3, 3}, {5, 1}, {5, 5}}
Output: 6

Approach: The given problem can be solved using basic combinatorics. Since all the bishops that lie on the same diagonal will attack each other, all possible pairs of bishops that are on the same diagonal that can be formed will attack each other. Therefore, traverse the matrix for all diagonals in both left and right directions and count the number of bishops on the current diagonal in a variable cnt. Now for each diagonal, the number of attacking bishops will be ^cntC₂.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
int board[20][20];
 
int countPairs(int N, vector<pair<int, int> > bishops)
{
    // Set all bits to 0
    memset(board, 0, sizeof(board));
 
    // Set all the bits
    // having bishop to 1
    for (int i = 0; i < bishops.size(); i++) {
        board[bishops[i].first][bishops[i].second] = 1;
    }
 
    // Stores the final answer
    int ans = 0;
 
    // Loop to traverse the matrix
    // diagonally in left direction
    for (int s = 2; s <= 2 * N; s++) {
 
        // Stores count of bishop
        // in the current diagonal
        int cnt = 0;
 
        for (int i = 1, j = s - i;
             max(i, j) <= min(N, s - 1); i++, j--) {
            if (board[j][i - j] == 1)
 
                // Update cnt
                cnt++;
        }
 
        // Update the answer
        if (cnt > 1)
            ans += ((cnt + 1) * cnt) / 2;
    }
 
    // Loop to traverse the matrix
    // diagonally in right direction
    for (int s = 2; s <= 2 * N; s++) {
 
        // Stores count of bishop
        // in the current diagonal
        int cnt = 0;
 
        for (int i = 1, j = s - i;
             max(i, j) <= min(N, s - 1); i++, j--) {
            if (board[i][N - j + 1] == 1)
 
                // Update cnt
                cnt++;
        }
 
        // Update the answer
        if (cnt > 1)
            ans += ((cnt + 1) * cnt) / 2;
    }
 
    // Return answer
    return ans;
}
 
// Driver code
int main()
{
    int N = 10;
    vector<pair<int, int> > bishops = {
        { 1, 1 }, { 1, 5 }, { 3, 3 }, { 5, 1 }, { 5, 5 }
    };
 
    cout << countPairs(N, bishops);
 
    return 0;
}

Java

import java.util.*;
class GFG
{
  static int [][]board = new int[20][20];
 
  static int countPairs(int N, int[][] bishops)
  {
 
    // Set all the bits
    // having bishop to 1
    for (int i = 0; i < bishops.length; i++) {
      board[bishops[i][0]][bishops[i][1]] = 1;
    }
 
    // Stores the final answer
    int ans = 0;
 
    // Loop to traverse the matrix
    // diagonally in left direction
    for (int s = 2; s <= 2 * N; s++) {
 
      // Stores count of bishop
      // in the current diagonal
      int cnt = 0;
 
      for (int i = 1, j = s - i;
           Math.max(i, j) <= Math.min(N, s - 1)&&i-j>0; i++, j--) {
        if (board[j][i - j] == 1)
 
          // Update cnt
          cnt++;
      }
 
      // Update the answer
      if (cnt > 1)
        ans += ((cnt + 1) * cnt) / 2;
    }
 
    // Loop to traverse the matrix
    // diagonally in right direction
    for (int s = 2; s <= 2 * N; s++) {
 
      // Stores count of bishop
      // in the current diagonal
      int cnt = 0;
 
      for (int i = 1, j = s - i;
           Math.max(i, j) <= Math.min(N, s - 1); i++, j--) {
        if (board[i][N - j + 1] == 1)
 
          // Update cnt
          cnt++;
      }
 
      // Update the answer
      if (cnt > 1)
        ans += ((cnt + 1) * cnt) / 2;
    }
 
    // Return answer
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N = 10;
    int[][] bishops = {
      { 1, 1 }, { 1, 5 }, { 3, 3 }, { 5, 1 }, { 5, 5 }
    };
 
    System.out.print(countPairs(N, bishops));
 
  }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program for above approach
board = [[0 for i in range(20)] for j in range(20)]
 
def countPairs(N, bishops):
 
    # Set all the bits
    # having bishop to 1
    for i in range(len(bishops)):
        board[bishops[i][0]][bishops[i][1]] = 1
 
    # Stores the final answer
    ans = 0
 
    # Loop to traverse the matrix
    # diagonally in left direction
    for s in range(2, (2 * N) + 1):
 
        # Stores count of bishop
        # in the current diagonal
        cnt = 0
 
        i = 1
        j = s - i
        while(max(i, j) <= min(N, s - 1)):
            if (board[j][i - j] == 1):
                # Update cnt
                cnt += 1
            i += 1
            j -= 1
 
        # Update the answer
        if (cnt > 1):
            ans += ((cnt + 1) * cnt) // 2
 
    # Loop to traverse the matrix
    # diagonally in right direction
    for s in range(2, (2 * N) + 1):
 
        # Stores count of bishop
        # in the current diagonal
        cnt = 0
 
        i = 1
        j = s - i
        while(max(i, j) <= min(N, s - 1)):
            
            if (board[i][N - j + 1] == 1):
                # Update cnt
                cnt += 1
            i += 1
            j -= 1
 
        # Update the answer
        if (cnt > 1):
            ans += ((cnt + 1) * cnt) // 2
 
    # Return answer
    return ans
 
# Driver code
N = 10
bishops = [[1, 1], [1, 5], [3, 3], [5, 1], [5, 5]]
print(countPairs(N, bishops))
 
# This code is contributed by gfgking

C#

using System;
class GFG
{
    static int[,] board = new int[20,20];
    static int countPairs(int N, int[,] bishops)
    {
 
        // Set all the bits
        // having bishop to 1
        for (int i = 0; i < bishops.GetLength(0); i++)
        {
            board[bishops[i,0], bishops[i,1]] = 1;
        }
 
        // Stores the final answer
        int ans = 0;
 
        // Loop to traverse the matrix
        // diagonally in left direction
        for (int s = 2; s <= 2 * N; s++)
        {
 
            // Stores count of bishop
            // in the current diagonal
            int cnt = 0;
 
            for (int i = 1, j = s - i;
                 Math.Max(i, j) <= Math.Min(N, s - 1) && i - j > 0; i++, j--)
            {
                if (board[j,i - j] == 1)
 
                    // Update cnt
                    cnt++;
            }
 
            // Update the answer
            if (cnt > 1)
                ans += ((cnt + 1) * cnt) / 2;
        }
 
        // Loop to traverse the matrix
        // diagonally in right direction
        for (int s = 2; s <= 2 * N; s++)
        {
 
            // Stores count of bishop
            // in the current diagonal
            int cnt = 0;
 
            for (int i = 1, j = s - i;
                 Math.Max(i, j) <= Math.Min(N, s - 1); i++, j--)
            {
                if (board[i,N - j + 1] == 1)
 
                    // Update cnt
                    cnt++;
            }
 
            // Update the answer
            if (cnt > 1)
                ans += ((cnt + 1) * cnt) / 2;
        }
 
        // Return answer
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        int N = 10;
        int[,] bishops = new int[5, 2]{{ 1, 1 }, { 1, 5 }, { 3, 3 }, { 5, 1 }, { 5, 5 }};
 
        Console.Write(countPairs(N, bishops));
 
    }
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

<script>
         
    // JavaScript program for above approach
    let board = new Array(20).fill(0).map(() => new Array(20).fill(0));
 
    const countPairs = (N, bishops) => {
 
        // Set all the bits
        // having bishop to 1
        for (let i = 0; i < bishops.length; i++) {
            board[bishops[i][0]][bishops[i][1]] = 1;
        }
 
        // Stores the final answer
        let ans = 0;
 
        // Loop to traverse the matrix
        // diagonally in left direction
        for (let s = 2; s <= 2 * N; s++) {
 
            // Stores count of bishop
            // in the current diagonal
            let cnt = 0;
 
            for (let i = 1, j = s - i;
                Math.max(i, j) <= Math.min(N, s - 1); i++, j--) {
                if (board[j][i - j] == 1)
 
                    // Update cnt
                    cnt++;
            }
 
            // Update the answer
            if (cnt > 1)
                ans += ((cnt + 1) * cnt) / 2;
        }
 
        // Loop to traverse the matrix
        // diagonally in right direction
        for (let s = 2; s <= 2 * N; s++) {
 
            // Stores count of bishop
            // in the current diagonal
            let cnt = 0;
 
            for (let i = 1, j = s - i;
                Math.max(i, j) <= Math.min(N, s - 1); i++, j--) {
                if (board[i][N - j + 1] == 1)
 
                    // Update cnt
                    cnt++;
            }
 
            // Update the answer
            if (cnt > 1)
                ans += ((cnt + 1) * cnt) / 2;
        }
 
        // Return answer
        return ans;
    }
 
    // Driver code
    let N = 10;
    let bishops = [
        [1, 1], [1, 5], [3, 3], [5, 1], [5, 5]
    ];
 
    document.write(countPairs(N, bishops));
 
// This code is contributed by rakeshsahni
 
</script>

Output

Time Complexity: O(N * N)
Auxiliary Space: O(N * N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Count pair of bishops that will attack each other on a N x N chessboard

C++

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

One of the best cameras for travel vloggers just got a massive price cut

Google is working on vertical tabs for Chrome

Gemini can now tell you whether that image is real or AI-generated

Google Phone could soon let urgent calls cut through DND

EDITOR PICKS

One of the best cameras for travel vloggers just got a massive price cut

Google is working on vertical tabs for Chrome

Gemini can now tell you whether that image is real or AI-generated

POPULAR POSTS

One of the best cameras for travel vloggers just got a massive price cut

Google is working on vertical tabs for Chrome

Gemini can now tell you whether that image is real or AI-generated

POPULAR CATEGORY

ABOUT US

FOLLOW US