[Community Puzzle] Chess cavalry

Puzzles
#1

https://www.codingame.com/training/hard/chess-cavalry

Send your feedback or ask for help here!

#2

3 posts were merged into an existing topic: Detection of Impossible in Chess Cavalry

#3

I have an iterative deepening depth-first search solution for Chess Cavalry. It works, but I have to manually cut off the maximum depth of the search at an arbitrary depth. Does anyone have any hints on how I would search this puzzle space and know for sure that it’s impossible? How would I know that I have exhausted all possible paths?

#4

Does your algorithm search a particular square more than once? If so, I suggest tweaking your algorithm so that this doesn’t happen. That way you will never search more nodes than there are empty squares.

Lookup flood fill: fixed memory method, it is very useful for a number of problems (although you will need to apply it using the knight’s movement).

2 Likes
#5

Your algorithm should remember if a square has been already visited or not.

2 Likes
#6

Every tests are ok
after submit, only test 4 ‘Protected king’ doesnt work.
Have you got other examples to understand pb and go through ?

[Community Puzzle] Chess cavalry
#7

Some variations based on test 4 :

8 8        8 8        8 8
....#...   ....#..B   ....#...
....##..   ....##..   ....##..
..E..#..   ..E..#..   ..E..#..
#...##..   #...##..   #...##..
.###...B   .###....   .###....
........   ........   ..B.....
........   ........   ........
........   ........   ........
=> 5       => 5       => 3
3 Likes
#8

Thanks a lot !!

and it goes bad for both… grrr.
Fyi i am using a BFS chess knight moves as “neighbours”