I have been doing some programming contest problems, and I have noticed that many of them involve something along the lines of "get the minimum number of steps necessary to achieve a certain goal".
Examples:
- Given the position of a knight and certain pawns in a chessboard, what is the minimum number of jumps the knight has to do to kill all the pawns?
- Given a parking lot with disordered cars labeled alphabetically, a "move" is the process of taking a car and inserting it elsewhere. What is the minimum number of moves to get this parking lot ordered?
So, many puzzles seem to share this structure: given a scenario, some rules, and a set of "operations", determine the least amount of operations to achieve a specific goal.
There's a twist in some of these puzzles though - sometimes, the puzzles will also ask if it is impossible to achieve.
I have discovered that I am particularly terrible with this kind of puzzles. In fact, I don't think I have ever solved them in an elegant way ever.
I'm not sure how to "test all cases", "pick the shortest one" or "determine it is impossible". Can you advice me here?
For the sake of the question, we can base ourselves on the chess puzzle:
Example Problem
We got a chessboard. Each square is labeled with a number (which represents the position), from 1 to 64.
(Possible) Input
2 8 31 13
This means "two pawns, on positions 8 and 31. The knight is on position 13."
Output
2
Two steps. From position 13
, the knight can jump to 8
, and from 8
, it can jump to 31
.
The Question
How can I approach this kind of problem? I solved the chess one by generating a list of all possible steps and then I picked the shortest one. But that was very slow.