Need explanation of question

#1

can u briefly explain the question i am unable to understand much

#2

and what will be the back tracking condition and why will we need to backtrack in this?

#3

@kingshuk441
Hi,
the question has a n*n board where not all cells of the board are allowed to be used ie the knight cannot be placed at those cells
now u are required to tell the minimum no of possible cells that the can not be traced by the knight
u basically need to maxmimise the cells that the knight visits in on e journey

#4

in board based question where u have a dfs call
u change the current cell as visited
after all 8 directions are called u
make it back to unvisited ( backtracking)

incase u are unable to code i`ll provide u the code

#5

i get confused on which step backtrack is used?i think after a knight checked all possible paths then u have to backtrack is it?

#6

if at a particular point if a knight can can move in all directions then why backtracking is needed?

#7
#8

int this code i am just printing all movements of knight in board plz help me in rectifying this

#9

u are updating the baord value when u move to next position in order to get back and u need to revert that change on the way back

#10

@kingshuk441
here we are replacing the cell with the count ( that is traced in case max cells are ) visited
the i have used
check(0,0,1,sol); to print this matrix
increasing value tells which cell is visited in which order i have tried to show with arrows.

since 1*1 index is the only cell which was never viisted in the max visited config , justifies the solution

image
image1914×807 12.1 KB

#11

ok i got the question but in my code the values for 4*4 or more is not working (15 is not displaying and 11 is displayed 2 times)

#12

plz check the code and tell the error

#13

why this 11 is printing in this as no path is there to get that cell

#14

@chhavibansal
You already are following this thread and the code, so can you help out here,
I just acknowledged this doubt, thought it was a new one.

#15

See
u 15 is not occuring because for the 4*4 board it is possible to traverse just 15 cells at max
leaving the 16th cell unatteneded

#16

yr yeh basically exact configuration nhi bta rha ki knight konse peh land karega jub max cells traverse honge

we are counting the max no of cells that can be traversed

refer this code:

@mahimahans111
if u have idea to print that exact path in which least no of cells are left unvisited please help him out.

#17

if u get the answer plz tell me also

#18

@kingshuk441 hey the chess board is not placable positions( where nights can be kept) 1 denotes yes knight can be placed , 0 denotes the knight is not placable, invalid position

so the question asks u the maximum no of positions the knight can travell starting from 0,0
u have a dfs call for all 8 possible moves from each cell

Minimize the no of unvisited cells means that knight is able to visit the maximum no of valid positions in the board.
eg:
3
1 1 1
1 1 1
1 1 1
all board positions are 1
so maximum visible cells are 9
now i start the knight from 0,0 have all 8 dfs call at each position
getting to see that knight can move on 8 valid cells at max
hence 9-8 == 1 is the answer
1 cell is left unvisited

See this code for reference:https://ide.codingblocks.com/s/220139

#19

yes i have done this ,but my question is that i want to print the path the knight is moving as a 2d array

#20

@kingshuk441 hey uske lie app visited array me mark krlo jha jha gya hai woh and base case me us path ko print kdro.