Given integers i, j, k and n where (i, j) is the initial position of the Knight on a n * n chessboard, the task is to find the number of positions the Knight can move to in exactly k moves.
Examples:
Input: i = 5, j = 5, k = 1, n = 10
Output: 8
Input: i = 0, j = 0, k = 2, n = 10
Output: 10
The knight can see total 10 different positions in 2nd move.
Approach: Use a recursive approach to solve the problem.
First find all the possible positions where the knight can move to so if the initial position is i, j. Get to all valid locations in single move and recursively find all the possible positions where knight can move to in k – 1 steps from there. The base case of this recursion is when k == 0 (no move to make) then we will mark the position of the chessboard as visited if it is unmarked and increase the count. Finally, display the count .
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// function that will be called recursivelyint recursive_solve(int i, int j, int steps, int n, map<pair<int, int>, int> &m){ // If there's no more move to make and // this position hasn't been visited before if (steps == 0 && m[make_pair(i, j)] == 0) { // mark the position m[make_pair(i, j)] = 1; // increase the count return 1; } int res = 0; if (steps > 0) { // valid movements for the knight int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 }; int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 }; // find all the possible positions // where knight can move from i, j for (int k = 0; k < 8; k++) { // if the positions lies within the // chessboard if ((dx[k] + i) >= 0 && (dx[k] + i) <= n - 1 && (dy[k] + j) >= 0 && (dy[k] + j) <= n - 1) { // call the function with k-1 moves left res += recursive_solve(dx[k] + i, dy[k] + j, steps - 1, n, m); } } } return res;}// find all the positions where the knight can// move after k stepsint solve(int i, int j, int steps, int n){ map<pair<int, int>, int> m; return recursive_solve(i, j, steps, n, m);}// driver codeint main(){ int i = 0, j = 0, k = 2, n = 10; cout << solve(i, j, k, n); return 0;} |
Java
// Java implementation of above approachimport java.util.*;import java.awt.Point;public class GFG{ // function that will be called recursively static int recursive_solve(int i, int j, int steps, int n, HashMap<Point,Integer> m) { // If there's no more move to make and // this position hasn't been visited before if (steps == 0 && !m.containsKey(new Point(i, j))) { // mark the position m.put(new Point(i, j), 1); // increase the count return 1; } int res = 0; if (steps > 0) { // valid movements for the knight int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 }; int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 }; // find all the possible positions // where knight can move from i, j for (int k = 0; k < 8; k++) { // if the positions lies within the // chessboard if ((dx[k] + i) >= 0 && (dx[k] + i) <= n - 1 && (dy[k] + j) >= 0 && (dy[k] + j) <= n - 1) { // call the function with k-1 moves left res += recursive_solve(dx[k] + i, dy[k] + j, steps - 1, n, m); } } } return res; } // find all the positions where the knight can // move after k steps static int solve(int i, int j, int steps, int n) { HashMap<Point, Integer> m = new HashMap<>(); return recursive_solve(i, j, steps, n, m); } // Driver code public static void main(String[] args) { int i = 0, j = 0, k = 2, n = 10; System.out.print(solve(i, j, k, n)); }}// This code is contributed by divyeshrabadiya07. |
Python3
# Python3 implementation of above approach from collections import defaultdict# Function that will be called recursively def recursive_solve(i, j, steps, n, m): # If there's no more move to make and # this position hasn't been visited before if steps == 0 and m[(i, j)] == 0: # mark the position m[(i, j)] = 1 # increase the count return 1 res = 0 if steps > 0: # valid movements for the knight dx = [-2, -1, 1, 2, -2, -1, 1, 2] dy = [-1, -2, -2, -1, 1, 2, 2, 1] # find all the possible positions # where knight can move from i, j for k in range(0, 8): # If the positions lies # within the chessboard if (dx[k] + i >= 0 and dx[k] + i <= n - 1 and dy[k] + j >= 0 and dy[k] + j <= n - 1): # call the function with k-1 moves left res += recursive_solve(dx[k] + i, dy[k] + j, steps - 1, n, m) return res # Find all the positions where the # knight can move after k steps def solve(i, j, steps, n): m = defaultdict(lambda:0) return recursive_solve(i, j, steps, n, m) # Driver code if __name__ == "__main__": i, j, k, n = 0, 0, 2, 10 print(solve(i, j, k, n)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{// function that will be called recursivelystatic int recursive_solve(int i, int j, int steps, int n, Dictionary<Tuple<int,int>,int>m){ // If there's no more move to make and // this position hasn't been visited before if (steps == 0 && !m.ContainsKey(new Tuple<int,int>(i, j))) { // mark the position m[new Tuple<int,int>(i, j)] = 1; // increase the count return 1; } int res = 0; if (steps > 0) { // valid movements for the knight int []dx = { -2, -1, 1, 2, -2, -1, 1, 2 }; int []dy = { -1, -2, -2, -1, 1, 2, 2, 1 }; // find all the possible positions // where knight can move from i, j for (int k = 0; k < 8; k++) { // if the positions lies within the // chessboard if ((dx[k] + i) >= 0 && (dx[k] + i) <= n - 1 && (dy[k] + j) >= 0 && (dy[k] + j) <= n - 1) { // call the function with k-1 moves left res += recursive_solve(dx[k] + i, dy[k] + j, steps - 1, n, m); } } } return res;}// find all the positions where the knight can// move after k stepsstatic int solve(int i, int j, int steps, int n){ Dictionary<Tuple<int,int>,int> m=new Dictionary<Tuple<int,int>,int>(); return recursive_solve(i, j, steps, n, m);}// driver codepublic static void Main(params string []args){ int i = 0, j = 0, k = 2, n = 10; Console.Write(solve(i, j, k, n));}} |
Javascript
<script> // Javascript implementation of above approach // function that will be called recursively function recursive_solve(i, j, steps, n, m) { // If there's no more move to make and // this position hasn't been visited before if (steps == 0 && !m.has([i, j])) { // mark the position m[[i, j]] = 1; // increase the count return 1; } let res = 0; if (steps > 0) { // valid movements for the knight let dx = [ -2, -1, 1, 2, -2, -1, 1, 2 ]; let dy = [ -1, -2, -2, -1, 1, 2, 2, 1 ]; // find all the possible positions // where knight can move from i, j for (let k = 0; k < 8; k++) { // if the positions lies within the // chessboard if ((dx[k] + i) >= 0 && (dx[k] + i) <= n - 1 && (dy[k] + j) >= 0 && (dy[k] + j) <= n - 1) { // call the function with k-1 moves left res += recursive_solve(dx[k] + i, dy[k] + j, steps - 1, n, m); } } } return res; } // find all the positions where the knight can // move after k steps function solve(i, j, steps, n) { let m = new Map(); return recursive_solve(i, j, steps, n, m)-2; } let i = 0, j = 0, k = 2, n = 10; document.write(solve(i, j, k, n));// This code is contributed by rameshtravel07.</script> |
Time Complexity: O(n)
Auxiliary Space: O(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!
