# Puzzle solving: Minimum number of steps to achieve a goal

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

# 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.

• A knight on a regular 8x8 chessboard cannot reach a certain position? Assumed I remember the rules of chess correctly, I am pretty sure a knight can reach any position (of course, not in one step). And what you asked about finding good solutions: in general, that is the theory of optimization, and there have been written lots of books about it. Here is a free one about global optimization: it-weise.de/projects/book.pdf Apr 23, 2013 at 20:47
• For the specifics of the knight's movement possibilities, look at the knight's tour.
– user40980
Apr 23, 2013 at 20:55
• Oh dear. Didn't realize that. I will modify my question accordingly. Apr 23, 2013 at 21:01
• For this problem, glance at Knight's Shortest Path Chess Question to see some code and analysis of this problem.
– user40980
Apr 23, 2013 at 21:15
• You might find the Prolog programming language to be of interest for this kind of problem. Support for "test all cases", "pick the shortest one" and "determine it is impossible" is mostly built in. This removes much of the boilerplate in writing basic search algorithms. Apr 24, 2013 at 1:59