Possible moves of knight
Given a chess board of dimension m * n. Find number of possible moves where knight can be moved on a chessboard from given position. If mat[i][j] = 1 then the block is filled by something else, otherwise empty. Assume that board consist of all pieces of same color, i.e., there are no blocks being attacked.
Examples:
Input : mat[][] = {{1, 0, 1, 0}, {0, 1, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 1}} pos = (2, 2) Output : 4 Knight can moved from (2, 2) to (0, 1), (0, 3), (1, 0) and (3, 0).
We can observe that knight on a chessboard moves either:
- Two moves horizontal and one move vertical
- Two moves vertical and one move horizontal
The idea is to store all possible moves of knight and then count the number of valid moves. A move will be invalid if:
- A block is already occupied by another piece.
- Move is out of the chessboard.
Implementation:
C++
// CPP program to find number of possible moves of knight #include <bits/stdc++.h> #define n 4 #define m 4 using namespace std; // To calculate possible moves int findPossibleMoves( int mat[n][m], int p, int q) { // All possible moves of a knight int X[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; int Y[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; int count = 0; // Check if each possible move is valid or not for ( int i = 0; i < 8; i++) { // Position of knight after move int x = p + X[i]; int y = q + Y[i]; // count valid moves if (x >= 0 && y >= 0 && x < n && y < m && mat[x][y] == 0) count++; } // Return number of possible moves return count; } // Driver program to check findPossibleMoves() int main() { int mat[n][m] = { { 1, 0, 1, 0 }, { 0, 1, 1, 1 }, { 1, 1, 0, 1 }, { 0, 1, 1, 1 } }; int p = 2, q = 2; cout << findPossibleMoves(mat, p, q); return 0; } |
Java
// Java program to find number of possible moves of knight public class Main { public static final int n = 4 ; public static final int m = 4 ; // To calculate possible moves static int findPossibleMoves( int mat[][], int p, int q) { // All possible moves of a knight int X[] = { 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 }; int Y[] = { 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 }; int count = 0 ; // Check if each possible move is valid or not for ( int i = 0 ; i < 8 ; i++) { // Position of knight after move int x = p + X[i]; int y = q + Y[i]; // count valid moves if (x >= 0 && y >= 0 && x < n && y < m && mat[x][y] == 0 ) count++; } // Return number of possible moves return count; } // Driver program to check findPossibleMoves() public static void main(String[] args) { int mat[][] = { { 1 , 0 , 1 , 0 }, { 0 , 1 , 1 , 1 }, { 1 , 1 , 0 , 1 }, { 0 , 1 , 1 , 1 } }; int p = 2 , q = 2 ; System.out.println(findPossibleMoves(mat, p, q)); } } |
Python3
# Python3 program to find number # of possible moves of knight n = 4 ; m = 4 ; # To calculate possible moves def findPossibleMoves(mat, p, q): global n, m; # All possible moves of a knight X = [ 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 ]; Y = [ 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 ]; count = 0 ; # Check if each possible move # is valid or not for i in range ( 8 ): # Position of knight after move x = p + X[i]; y = q + Y[i]; # count valid moves if (x > = 0 and y > = 0 and x < n and y < m and mat[x][y] = = 0 ): count + = 1 ; # Return number of possible moves return count; # Driver code if __name__ = = '__main__' : mat = [[ 1 , 0 , 1 , 0 ], [ 0 , 1 , 1 , 1 ], [ 1 , 1 , 0 , 1 ], [ 0 , 1 , 1 , 1 ]]; p, q = 2 , 2 ; print (findPossibleMoves(mat, p, q)); # This code is contributed by 29AjayKumar |
C#
// C# program to find number of // possible moves of knight using System; class GFG { static int n = 4; static int m = 4; // To calculate // possible moves static int findPossibleMoves( int [,]mat, int p, int q) { // All possible moves // of a knight int []X = { 2, 1, -1, -2, -2, -1, 1, 2 }; int []Y = { 1, 2, 2, 1, -1, -2, -2, -1 }; int count = 0; // Check if each possible // move is valid or not for ( int i = 0; i < 8; i++) { // Position of knight // after move int x = p + X[i]; int y = q + Y[i]; // count valid moves if (x >= 0 && y >= 0 && x < n && y < m && mat[x, y] == 0) count++; } // Return number // of possible moves return count; } // Driver Code static public void Main () { int [,]mat = { { 1, 0, 1, 0 }, { 0, 1, 1, 1 }, { 1, 1, 0, 1 }, { 0, 1, 1, 1 }}; int p = 2, q = 2; Console.WriteLine(findPossibleMoves(mat, p, q)); } } // This code is contributed by m_kit |
PHP
<?php // PHP program to find number // of possible moves of knight $n = 4; $m = 4; // To calculate possible moves function findPossibleMoves( $mat , $p , $q ) { global $n ; global $m ; // All possible moves // of a knight $X = array (2, 1, -1, -2, -2, -1, 1, 2); $Y = array (1, 2, 2, 1, -1, -2, -2, -1); $count = 0; // Check if each possible // move is valid or not for ( $i = 0; $i < 8; $i ++) { // Position of // knight after move $x = $p + $X [ $i ]; $y = $q + $Y [ $i ]; // count valid moves if ( $x >= 0 && $y >= 0 && $x < $n && $y < $m && $mat [ $x ][ $y ] == 0) $count ++; } // Return number // of possible moves return $count ; } // Driver Code $mat = array ( array (1, 0, 1, 0), array (0, 1, 1, 1), array (1, 1, 0, 1), array (0, 1, 1, 1)); $p = 2; $q = 2; echo findPossibleMoves( $mat , $p , $q ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to find number of possible moves of knight let n = 4; let m = 4; // To calculate possible moves function findPossibleMoves(mat, p, q) { // All possible moves of a knight let X = [ 2, 1, -1, -2, -2, -1, 1, 2 ]; let Y = [ 1, 2, 2, 1, -1, -2, -2, -1 ]; let count = 0; // Check if each possible move is valid or not for (let i = 0; i < 8; i++) { // Position of knight after move let x = p + X[i]; let y = q + Y[i]; // count valid moves if (x >= 0 && y >= 0 && x < n && y < m && mat[x][y] == 0) count++; } // Return number of possible moves return count; } let mat = [ [ 1, 0, 1, 0 ], [ 0, 1, 1, 1 ], [ 1, 1, 0, 1 ], [ 0, 1, 1, 1 ] ]; let p = 2, q = 2; document.write(findPossibleMoves(mat, p, q)); </script> |
Output
4
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us