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.
8
There are more than a few different ideas one could employ on these kinds of problems:
Breadth-first search would be one technique to find the minimum moves for a problem that basically enumerates all possibilities. While this is brute force there can be some applications of this technique that can work quite well. The alternative to this is a depth-first search.
Dynamic programming would be another technique that may be used to generate answers assuming certain characteristics about the problem. This can be used if one can break down a problem into smaller pieces and then build up which way to go.
Greedy algorithms would be another heuristic that can be useful with these kinds of problems as “making change” would be a classic that is solved with this method.
Divide and conquer would be another strategy that can be employed to solve some types of computing problems. Mergesort would be an example of using this technique.
These are a few of the common methods that would be taught as part of an, “Introduction to Algorithm Design and Analysis” course that covers how to use these techniques.