0

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
  • 1
    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
    – Doc Brown
    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.
    – Saturn
    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
  • 1
    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.
    – Brian
    Apr 24, 2013 at 1:59

1 Answer 1

7

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.