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?
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
Your algorithm should remember if a square has been already visited or not.
2 Likes