An algorithm challenge

From: Raptor (bogus_at_none.com)
Date: 03/06/05

  • Next message: Maarten Wiltink: "Re: An algorithm challenge" 
    Date: Sun, 6 Mar 2005 03:01:34 -0800

    Working on a little puzzle program, a small diversion just for fun.

    Given a grid of 9, 16, or 25 buttons (let's select 16 for this example) laid
    out in a square, something like this:

    [01] [02] [03] [04]
    [05] [06] [07] [08]
    [09] [10] [11] [12]
    [13] [14] [15] [16]

    They can be numbered any way we like, if that makes the algorithm simpler
    or, even better, faster. Here are the rules:

    1. The object of the algorithm is to find all possible "paths"
       from a given starting point.
    2. We can start on any square we like.
    3. A path consists of at least one move onto an adjacent square.
    4. "Adjacent" is horizontal, vertical or diagonal. For example,
       the squares adjacent to 01 would be 02, 05, 06.
    5. The longest path will be 16 squares, the shortest 2.
    6. No path may use a square twice.

    Beginning at square 01, all one step paths are:
      01-02, 01-05, 01-06

    Beginning at square 01, the list of two step paths might start with:
      01-02-03
      01-02-05
      01-02-06
      01-02-07
      01-05-02
      01-05-06
      01-05-09
      01-05-10
      ...

    In some ways, I think the problem might be like the game of Life. Each
    square must "sense" who are its neighbors. From 06 one can step to the left,
    but from 05 one cannot. Anything on 05 must "know" nothing is to its left.

    The solution which first suggests itself to me is a table of all the
    adjacent squares of each square, then use a recursive algorithm to run down
    all the paths. Haven't tried anything yet though.

    The problem looked interesting enough from a theoretical perspective that I
    decided to float it by the group.

    R

  • Next message: Maarten Wiltink: "Re: An algorithm challenge"
    • Quantcast