Given the current position of a Knight as (i, j), find the count of different possible positions visited by a knight after N moves (in a 10 x 10 board).
Examples:
Input: i = 3, j = 3, n = 1
Output: 9
The Knight is initially at position [3][3]. After one move it can visit 8 more cellsInput: i = 3, j = 3, n = 2
Output: 35
Approach: The idea is simple, we start from a given position, try all possible moves. After every move, recursively call for n-1 moves. We need to ensure that we never visit a cell again. We make a visited boolean matrix which will serve as a visited matrix so that the positions do not get repeated. When we visit a position, mark that position as true in the matrix.
Steps:-
- Take a boolean visited matrix (10X10) and initialize all the cells as false (non-visited)
- Create two vectors with all possible moves of a knight. We find that there are 8 possible moves of a knight.
- Valid position = The knight is inside the boundaries of the board and the cell is non-visited.
- Call the method for the next valid position with n = n-1.
- If n == 0, return.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int N = 10;// All possible moves of the knight.// In X axis.vector<int> X = { 2, 1, -1, -2, -2, -1, 1, 2 };// In Y axis.vector<int> Y = { 1, 2, 2, 1, -1, -2, -2, -1 };void getCountRec(vector<vector<bool> >& board, int i, int j, int n){ // if n=0, we have our result. if (n == 0) return; for (int k = 0; k < 8; k++) { int p = i + X[k]; int q = j + Y[k]; // Condition for valid cells. if (p >= 0 && q >= 0 && p < 10 && q < N) { board[p][q] = true; getCountRec(board, p, q, n - 1); } }}int getCount(int i, int j, int n){ vector<vector<bool> > board(N, vector<bool>(N)); board[i][j] = true; // Call the recursive function to mark // visited cells. getCountRec(board, i, j, n); int cnt = 0; for (auto row : board) { for (auto cell : row) { if (cell) cnt++; } } return cnt;}// Driver Codeint main(){ int i = 3, j = 3, N = 2; cout << getCount(i, j, N) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{ static int N = 10;// All possible moves of the knight.// In X axis.static int[] X = { 2, 1, -1, -2, -2, -1, 1, 2 };// In Y axis.static int[] Y = { 1, 2, 2, 1, -1, -2, -2, -1 };static void getCountRec(boolean[][] board, int i, int j, int n){ // If n=0, we have our result. if (n == 0) return; for(int k = 0; k < 8; k++) { int p = i + X[k]; int q = j + Y[k]; // Condition for valid cells. if (p >= 0 && q >= 0 && p < 10 && q < N) { board[p][q] = true; getCountRec(board, p, q, n - 1); } }}static int getCount(int i, int j, int n){ boolean[][] board = new boolean[N][N]; board[i][j] = true; // Call the recursive function to mark // visited cells. getCountRec(board, i, j, n); int cnt = 0; for(boolean[] row : board) { for(boolean cell : row) { if (cell != false) cnt++; } } return cnt;}// Driver codepublic static void main(String[] args){ int i = 3, j = 3, N = 2; System.out.println(getCount(i, j, N));}}// This code is contributed by sanjoy_62 |
Python3
# Python program for the above approachSIZE = 10# All possible moves of the knight.# In X axis.X = [2, 1, -1, -2, -2, -1, 1, 2] # In Y axis.Y = [1, 2, 2, 1, -1, -2, -2, -1]def getCountRec(board, i, j, n): # If n=0, we have our result. if n == 0: return for k in range(8): p = i + X[k] q = j + Y[k] # Condition for valid cells. if p >= 0 and q >= 0 and p < 10 and q < SIZE: board[p][q] = True getCountRec(board,p,q,n-1) def getCount(i, j, n): board = [[False for i in range(SIZE)] for j in range(SIZE)] board[i][j] = True # Call the recursive function to mark # visited cells. getCountRec(board, i, j, n) cnt = 0 for row in board: for cell in row: if cell != False: cnt += 1 return cnt# Driver code i = 3j = 3N = 2print(getCount(i, j, N))# This code is contributed by rdtank. |
C#
// C# program for the above approachusing System;class GFG{ static int N = 10; // All possible moves of the knight. // In X axis. static int [] X = { 2, 1, -1, -2, -2, -1, 1, 2 }; // In Y axis. static int [] Y = { 1, 2, 2, 1, -1, -2, -2, -1 }; static void getCountRec(bool[,] board, int i, int j, int n) { // If n=0, we have our result. if (n == 0) return; for(int k = 0; k < 8; k++) { int p = i + X[k]; int q = j + Y[k]; // Condition for valid cells. if (p >= 0 && q >= 0 && p < 10 && q < N) { board[p, q] = true; getCountRec(board, p, q, n - 1); } } } static int getCount(int i, int j, int n) { bool [, ] board = new bool[N, N]; board[i, j] = true; // Call the recursive function to mark // visited cells. getCountRec(board, i, j, n); int cnt = 0; foreach(bool cell in board) { if(cell != false) cnt++; } return cnt; } // Driver code public static void Main() { int i = 3, j = 3, N = 2; Console.WriteLine(getCount(i, j, N)); }}// This code is contributed by ihritik |
Javascript
<script>// JavaScript implementation of the approachconst SIZE = 10;// All possible moves of the knight.// In X axis.let X = [ 2, 1, -1, -2, -2, -1, 1, 2 ];// In Y axis.let Y = [ 1, 2, 2, 1, -1, -2, -2, -1 ];function getCountRec(board,i,j,n){ // if n=0, we have our result. if (n == 0) return; for (let k = 0; k < 8; k++) { let p = i + X[k]; let q = j + Y[k]; // Condition for valid cells. if (p >= 0 && q >= 0 && p < 10 && q < SIZE) { board[p][q] = true; getCountRec(board, p, q, n - 1); } }}function getCount(i, j, n){ let board = new Array(SIZE).fill(0).map(()=>new Array(N)); board[i][j] = true; // Call the recursive function to mark // visited cells. getCountRec(board, i, j, n); let cnt = 0; for (let row of board) { for (let cell of row) { if (cell) cnt++; } } return cnt;}// Driver Codelet i = 3, j = 3,N = 2;document.write(getCount(i, j, N),"</br>");// This code is contributed by shinjanpatra</script>// JavaScript implementation of the approachconst SIZE = 10;// All possible moves of the knight.// In X axis.let X = [ 2, 1, -1, -2, -2, -1, 1, 2 ];// In Y axis.let Y = [ 1, 2, 2, 1, -1, -2, -2, -1 ];function getCountRec(board,i,j,n){ // if n=0, we have our result. if (n == 0) return; for (let k = 0; k < 8; k++) { let p = i + X[k]; let q = j + Y[k]; // Condition for valid cells. if (p >= 0 && q >= 0 && p < 10 && q < SIZE) { board[p][q] = true; getCountRec(board, p, q, n - 1); } }}function getCount(i, j, n){ let board = new Array(SIZE).fill(0).map(()=>new Array(N)); board[i][j] = true; // Call the recursive function to mark // visited cells. getCountRec(board, i, j, n); let cnt = 0; for (let row of board) { for (let cell of row) { if (cell) cnt++; } } return cnt;}// Driver Codelet i = 3, j = 3,N = 2;document.write(getCount(i, j, N),"</br>");// This code is contributed by shinjanpatra</script> |
Output:
35
Time Complexity: O(8^N) where N is the number of moves the knight can make.
Space Complexity: O(N^2), where N is the size of the chessboard. This is because we are using a 2D vector to store the visited cells on the board. The size of this vector is N x N.
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!
