Hints for this problem

#1

Hi,
I tried this problem , but its not working. please help me with java code

#2

@indrabijaynarayan,
Did you try writing the code? If yes, can you please share your code. If not, please elaborate which part are you not able to understand the question

This problem can be done using “recursion/dfs and similar” fashion. once you visit a cell, then visit all the cells that can be visited from this cell and also visit the cells that can be further visited from the next reachable cells.

#3

what would be the base case?

#4

@indrabijaynarayan,
if(i<0 || i>=10 || j<0 || j>=10 || board[i][j] == 0)
return;
ensures that we are not visiting any cell that is out of bounds or have been visited before

Also Since we have to do is find the minimum number of cells that the knight can not reach under the constraint that the knight may not move to any square that is not on the board and cannot rest in any spot more than once . here i am trying to find the maximum number of squares knight can visit in one go and the i will subtract it with total number of cells

I suggest solving this using recursion with backtracking . once you visit a cell, then visit all the cells that can be visited from this cell and also visit the cells that can be further visited from the next reachable cells. and keep tracking the number of cells you have visited in one traversal until there is no cell that you can visit further ,also keep marking the visited cell so that you don’t visit those cells again

#5

ok… and what would be positive base case.

#6

@indrabijaynarayan,
What do you mean by positive base case?

#7

the base case where we can add and print.

#8

@indrabijaynarayan,
You don’t have to add a positive base case. In case we don’t return follow the below pattern:

answer(i,j,count) : this is the state of function when i have reached position i,j from 0,0 by following some path and count denotes the number of cells i have visited in the path (not including the current square)

line 9-10 :
if(i<0 || i>=10 || j<0 || j>=10 || board[i][j] == 0)
return;

line 12 : board[i][j] = 0; : this is done to denote that this cell can’t be visited from now onwards
with this we are ensuring that the knight will not visit this cell again while traversing the path

line 13: hi = max(hi,count+1); , here hi , stores our answer i.e the maximum cells that can be visited in one go under the given constraint and count+1 is the count of cells i have visited including current cell,in the path traversed by the knight from (0,0) to (i,j) and if this value is greater than hi , then hi is updated
line 15-22 :
answer(i-1,j-2,count+1);
answer(i-2,j-1,count+1);
answer(i+1,j-2,count+1);
answer(i+2,j-1,count+1);
answer(i-1,j+2,count+1);
answer(i-2,j+1,count+1);
answer(i+1,j+2,count+1);
answer(i+2,j+1,count+1);
these are the possible position of cells that our knight can visit from (i,j) in one jump ,notice that we are increasing count by 1 to include cell i,j in the count
line 23 : board[i][j] = 1 Backtracking

In case you still have any doubt feel free to ask :slight_smile:

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.