# Count all possible visited cells of a knight after N moves

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:i = 3, j = 3, n = 1Output:9

The Knight is initially at position [3][3]. After one move it can visit 8 more cells

Input:i = 3, j = 3, n = 2Output: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 Code` `int` `main()` `{` ` ` `int` `i = 3, j = 3, N = 2;` ` ` `cout << getCount(i, j, N) << endl;` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `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 code` `public` `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` |

## C#

`// C# program for the above approach` `using` `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` |

**Output:**

35