Algo++ : Funky chess board

#1

From starting position i generated all possible positions for knight.
if generated position is 0 then return to previous position.
if generated position is 1 , change it to 0 ,so that we never recur for that position again and generate all possible positions
finally , positions where knight cannot reach will remain 1
so count no. of 1’s in final chess board

according to this solution 2 test cases are showing wrong answer

please correct my logic if required

code link : https://ide.codingblocks.com/s/100446

#2

Hi @amandahiya.3572
The problem is that you are not using backtracking and considering the mixture of all possible moves of the knights all together …we have to consider each path of it and count of the number of cells visited in that path and minimise that number. Your code simply counts the number of all the possible cells that the knight can reach in total.

That is ,you have find one path where the knight can cover the maximum no of cells and your knight has to stick to it without going back.

Here’s a testcase for you to understand

Input :
4
1 0 1 0
0 0 1 0
1 1 0 1
0 0 0 0

Expected Output : 2
Your Output : 0
Explanation : There are only two possible paths for the knight to traverse without going back .
( I am using 0 based indexing here )
Path 1 : (0,0) -> (2,1) -> (0,2) -> (2,3)
Path 2 : (0,0) -> (1,2) -> (2,0)

Clearly we would prefer Path 1 as it covers more nodes.
The no of nodes left out in path 1 were 2 and nodes left out in path 2 were 3.
Final answer will be 2 as Path 1 is the better one.
Hope this helps.

Here’s another testcase for you to try when you update your code.

Input :
10
1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1

Expected Output : 17

#3

ohh ! I misunderstood the question .But it is still showing wrong answer for me .Please help. code link : https://ide.codingblocks.com/s/100818

#4

@amandahiya.3572
It is possible to come to same cells from different paths and thus get different answers.
Consider this testcase for a better clarity :
Input :
4
1 0 0 0
0 0 1 0
0 1 0 0
0 1 0 1

Expected Output : 0
Your Output : 1

Explanation :
Ideal Path which the Knight should have taken is
(considering 0 based indexing starting from top-left corner)
(0,0) -> (2,1) -> (3,3) -> (1,2) -> (3,1)
This path covers all the 1’s and gives the answer 0.

Your code traverses a different path :
(0,0) -> (1,2) -> (3,3) -> (2,1)

And since its impossible to reach (3,1) from (2,1) , (3,1) remains unvisited and the code gives the answer as 1.

#5

yes, I understood , storing is a bad idea . I changed my code and now it is submitted . Thank you for your help

#6

bro…can you plz send me ur code