You are given a 8*8 chess board. Along with the chess board there is a Bishop placed on board and its position is known. Position of Bishop is given in form of two digit integer where both digits are greater than 0 and less than 9 (like 67 denotes 6th column and 7th row). Now your task is to find the number of ways in which you can place a pawn safely on the board.
Examples:Â
Input : Bishop’s Position = 11
Output : Safe Positions = 56Input : Bishop’s Position = 44
Output : Safe Positions = 50
Brute Force Approach : One of the basic approach is to iterate through all the 64 possible positions on chess board and check whether that position is safe or not. This approach will require much more time.
Better Approach: As we know that movement of Bishop is in diagonal manner so from any position on the chess board a Bishop can move in both direction of both diagonals. So, all the positions which does not lie on the way of diagonal movement of the given Bishop are the safe positions.Â
Now our task is to find the maximum length in all possible four direction from the position of Bishop.Â
Â
-> From any position a Bishop can move towards four corner that are (11, 18, 81, 88). So, we will try to find the find the maximum distance which the Bishop can move towards these corner.Â
Let position of bishop is i,j then:Â
- Distance towards 11 = min (mod(1-i), mod(1-j) ).
- Distance towards 18 = min (mod(1-i), mod(8-j) ).
- Distance towards 81 = min (mod(8-i), mod(1-j) ).
- Distance towards 88 = min (mod(8-i), mod(8-j) ).
Beside all these four, one position at which Bishop is already placed is also not safe so total number of unsafe position is sum of above results + 1. and total number of safe position is 64 -(sum+1).Â
C++
// CPP program to find total safe position// to place your Bishop#include<bits/stdc++.h>using namespace std;Â
// function to calc total safe positionint calcSafe(int pos){    // i,j denotes row and column of position of bishop    int j = pos % 10;    int i = pos /10;Â
    // calc distance in four direction    int dis_11 = min ( abs(1-i), abs (1-j));    int dis_18 = min ( abs(1-i), abs (8-j));    int dis_81 = min ( abs(8-i), abs (1-j));    int dis_88 = min ( abs(8-i), abs (8-j));Â
    // calc total sum of distance + 1 for unsafe positions    int sum = dis_11 + dis_18 + dis_81 + dis_88 + 1;Â
    // return total safe positions    return (64- sum);}Â
// driver functionint main(){Â Â Â Â int pos = 34;Â Â Â Â cout << "Safe Positions = " << calcSafe(pos);Â Â Â Â return 0;} |
Java
// Java program to find total safe position// to place your Bishopclass GFG{         // function to calc total safe position    static int calcSafe(int pos)    {                 // i,j denotes row and column of position of bishop        int j = pos % 10;        int i = pos /10;             // calc distance in four direction        int dis_11 = Math.min ( Math.abs(1-i), Math.abs (1-j));        int dis_18 = Math.min ( Math.abs(1-i), Math.abs (8-j));        int dis_81 = Math.min ( Math.abs(8-i), Math.abs (1-j));        int dis_88 = Math.min ( Math.abs(8-i), Math.abs (8-j));             // calc total sum of distance + 1 for unsafe positions        int sum = dis_11 + dis_18 + dis_81 + dis_88 + 1;             // return total safe positions        return (64- sum);    }             // Driver function    public static void main (String[] args)    {        int pos = 34;                 System.out.print("Safe Positions = "+calcSafe(pos));    }}Â
// This code is contributed by Anant Agarwal. |
Python3
# python program to find total safe# position to place your Bishopimport math Â
# function to calc total safe positiondef calcSafe(pos):         # i,j denotes row and column of    # position of bishop    j = pos % 10    i = pos /10Â
    # calc distance in four direction    dis_11 = min ( abs(1-i), abs (1-j))    dis_18 = min ( abs(1-i), abs (8-j))    dis_81 = min ( abs(8-i), abs (1-j))    dis_88 = min ( abs(8-i), abs (8-j))Â
    # calc total sum of distance + 1    # for unsafe positions    sum = (dis_11 + dis_18 + dis_81                         + dis_88 + 1)Â
    # return total safe positions    return (64- sum)Â
Â
# driver functionpos = 34print("Safe Positions = " , Â Â Â Â Â Â Â Â Â Â Â Â math.ceil(calcSafe(pos)))Â
# This code is contributed by Sam007 |
C#
// Program to find the total safe// positions to place your Bishopusing System;Â
class GFG {Â
    // function to calc total safe position    static int calcSafe(int pos)    {Â
        // i, j denotes row and column of        // position of bishop        int j = pos % 10;        int i = pos / 10;Â
        // calc distance in four direction        int dis_11 = Math.Min(Math.Abs(1 - i), Math.Abs(1 - j));        int dis_18 = Math.Min(Math.Abs(1 - i), Math.Abs(8 - j));        int dis_81 = Math.Min(Math.Abs(8 - i), Math.Abs(1 - j));        int dis_88 = Math.Min(Math.Abs(8 - i), Math.Abs(8 - j));Â
        // calc total sum of distance + 1        // for unsafe positions        int sum = dis_11 + dis_18 + dis_81 + dis_88 + 1;Â
        // return total safe positions        return (64 - sum);    }Â
    // Driver function    public static void Main()    {        int pos = 34;Â
        Console.WriteLine("Safe Positions = " + calcSafe(pos));    }}Â
// This code is contributed by vt_m. |
Javascript
<script>Â
// Javascript program to find total safe position// to place your BishopÂ
// function to calc total safe positionfunction calcSafe( pos){    // i,j denotes row and column of position of bishop    let j = pos % 10;    let i = Math.floor(pos /10);Â
    // calc distance in four direction    let dis_11 = Math.min( Math.abs(1-i), Math.abs(1-j));    let dis_18 = Math.min( Math.abs(1-i), Math.abs(8-j));    let dis_81 = Math.min( Math.abs(8-i), Math.abs(1-j));    let dis_88 = Math.min( Math.abs(8-i), Math.abs(8-j));Â
    // calc total sum of distance + 1 for unsafe positions    let sum = dis_11 + dis_18 + dis_81 + dis_88 + 1;Â
    // return total safe positions    return (64- sum);}Â
// driver code Â
    let pos = 34;    document.write("Safe Positions = " + calcSafe(pos));Â
</script> |
PHP
<?php// PHP program to find // total safe position// to place your BishopÂ
// function to calculate// total safe positionfunction calcSafe( $pos){         // i,j denotes row and     // column of position     // of bishop    $j = $pos % 10;    $i = $pos /10;Â
    // calc distance in four direction    $dis_11 = min(abs(1 - $i),                   abs (1 - $j));    $dis_18 = min(abs(1 - $i),                   abs (8 - $j));    $dis_81 = min(abs(8 - $i),                   abs (1 - $j));    $dis_88 = min(abs(8 - $i),                   abs (8 - $j));Â
    // calc total sum of     // distance + 1 for     // unsafe positions    $sum = $dis_11 + $dis_18 +            $dis_81 + $dis_88 + 1;Â
    // return total safe positions    return ceil(64- $sum);}Â
    // Driver Code    $pos = 34;    echo "Safe Positions = " ,calcSafe($pos);Â
// This code is contributed by vt_m.?> |
Output
Safe Positions = 52
Time Complexity: O(1)
Auxiliary Space: O(1)
Â
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
