Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

I am sure the majority of you enjoy good brain teasers and puzzles. A few years ago, I received a wooden puzzle for Christmas that apparently can be solved in as few as 16 moves (unverified). I have never came close and wanted to see if my fellow monks were up to the challenge.

This is a picture of the starting position. The object of the game is to get the large square (red dot) to the position at the bottom occupied by the 4 small squares (blue dots). You may only move pieces by sliding them.

The challenge is to write a program that will solve the puzzle in the fewest number of moves possible. Graphic solutions are not necessary, but would be cool. Any solution method will be eligible (golfed, regex, bruteforce, etc). The solution must be able to be verified using the real puzzle :-)

Cheers - L~R

The story behind the Setting Sun Puzzle can be found here

Update: It is definately not 16 moves as this site would suggest. The 16 step solution (don't peek) requires multiple moves to get to each step. My definition of "move" remains and the solution with the fewest moves still wins.

Replies are listed 'Best First'.
Re: Challenge: Setting Sun Puzzle
by thospel (Hermit) on Oct 04, 2004 at 17:53 UTC
    This puzzle (among many others) is discussed in Winning ways for your mathematical plays, volume 4 as "the donkey puzzle". They give general methods for how to attack this kind of puzzles and give a shortcut map for how to solve this particular one from any position to any other.

    But to keep the subject more to perl, here is a quick and dirty program I made to solve it. If I didn't make mistakes (unlikely), the solution is 90 moves.

    janitored by ybiC: Balanced <readmore> tags around codeblock to 'hide' solution.

      AFAICT, this is a correct solution! I will have to pick up the book as well as try and understand your code. Bravo.

      Cheers - L~R

Re: Challenge: Setting Sun Puzzle
by tye (Sage) on Oct 04, 2004 at 19:02 UTC

    Here is my solution.

    #!/usr/bin/perl -w use strict; # A board is a string of 35 characters showing current positions # and last move or two (so we don't just undo the last move): # ,----. ,----. ,----. ,----. ,----. ,----. ,----. ,----. # |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| # |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| |AXXB| # | HH | |HH< | |HH2 | |HH2 | |HH>2| |HH42| |HH42| |HH4v| # |C12D| |C12D| |C1^D| |C14D| |C14D| |C1^D| |C1D<| |C1D2| # |C34D| |C34D| |C34D| |C3^D| |C3 D| |C3 D| |C3D<| |C3D | # `----' `----' `----' `----' `----' `----' `----' `----' # H< H<2^ H<2^4^ ... # On the end of the board we keep all the moves needed. # We start with just one board and build the list of boards # we can get with one more move. $|= 1; my $start= "#####AXXB#AXXB# HH #C12D#C34D######"; my @boards= $start; my %double; @double{ qw( A< A> B< B> C< C> D< D> H^ Hv X< X> X^ Xv ) } = (1) x 14; my %offset= qw( < -1 > +1 ^ -5 v +5 ); my %size= qw( 1 1 2 1 3 1 4 1 A 2 B 2 C 2 D 2 H 2 X 4 ); my %back= qw( < > > < ^ v v ^ ); $back{' '}= ' '; my @MovedX; my $moves= 0; my $dupCount= 1; my %uniq; while( 1 ) { @MovedX= (); print "Considering ", 0+@boards, " of $dupCount boards after $moves moves...\n"; Dump( @boards ) if @ARGV; @boards= map MoveAny($_), @boards; $dupCount= @boards; @boards= grep { my $board= substr( $_, 0, 35 ); $board =~ tr[<>^v1234ABCDH] [ OOOO||||=]; ! $uniq{$board}++; } @boards; $moves++; # Dump( @MovedX ); } sub MoveAny { my( $board )= @_; my @boards; $board =~ /[<>v^ ]/g or die $board; my @gap= pos($board)-1; $board =~ /[<>v^ ]/g or die $board; push @gap, pos($board)-1; my %can; for my $gap ( @gap ) { my $skip= $back{substr($board,$gap,1,' ')}; for my $dir ( keys %offset ) { next if $skip eq $dir; my $off= $offset{$dir}; my $block= substr($board,$gap-$off,1); next if ! $size{$block}; if( ! $double{$block.$dir} || 2 <= ++$can{$block.$dir} ) { push @boards, MoveThis( $board, $block, $dir, $off ); } } } return @boards; } sub MoveThis { my( $board, $block, $dir, $off )= @_; my @pos; while( $board =~ /$block/g ) { last if 30 < pos($board); push @pos, pos($board)-1; } substr( $board, $_, 1, $dir ) for @pos; substr( $board, $_+$off, 1, $block ) for @pos; $board .= $block . $dir; Win($board) if $board =~ /XX[^#]##/; if( "X" eq $block ) { push @MovedX, $board; } return $board; } sub Dump { my( @all )= @_; while( @all ) { my @boards= splice( @all, 0, 8 ); for my $line ( 0 .. 6 ) { for my $board ( @boards ) { print " #", substr($board,5*$line,5); } print $/; } if( 1 == @boards ) { print " ", substr($boards[0],35); } else { for my $board ( @boards ) { printf " %-6s", substr(substr($board,35),-6); } } print $/; } } my $won; sub Win { return if $won++; my( $board )= @_; my @moves= substr($board,35) =~ /(..)/g; print "\n @moves\n\n"; $board= $start; my @boards= $board; for my $move ( @moves ) { my( $block, $dir )= $move =~ /(.)(.)/; substr( $board, 35 )= ''; $board =~ tr/<>^v/ /; $board= MoveThis( $board, $block, $dir, $offset{$dir} ); push @boards, $board; } Dump( @boards ); exit 0; }

    And the output:

    H< 2^ 2> H> C^ 3< 4< D< 2v H> 1^ 4^ 3> Cv 1< H< Bv 2v Bv X> A> 1^ 1^ C^ C^ 4< 3< D< 2< 2^ Bv H> D^ 3> 3> Dv Av 1> C^ 4^ D< Av Av 4> 4^ H< H< B^ 3> 2v B< 3^ 2> Bv H> Cv 1< 4^ H> A^ A^ B< 3< 3v Hv Xv 4> 1> C^ 4> 1> A^ D^ B^ 3< 3< 2< 2< Hv Xv 1v 1> A> B^ B^ X< 1v 4v 1v 4v A> B> C> D^ D^ X< 4< 1^ H^ 2> 3> 2> 3> Xv 4< 4< 1< 1< H^ 3^ 3> X>

    I didn't care to define "one move" to include moving the same piece more than one square, so 112 moves is the minimum w/o folding such moves together.

    - tye        

Re: Challenge: Setting Sun Puzzle
by itub (Priest) on Oct 04, 2004 at 20:11 UTC
    Here's my solution. It's not as short as some of the others because it is object-oriented/array based instead of using strings and regexes, but it agrees that the solution needs 112 "simple moves".

    The code:

    and the solution:

Re: Challenge: Setting Sun Puzzle
by bobf (Monsignor) on Oct 05, 2004 at 04:35 UTC

    Very interesting challenge!

    Here is my solution. I didn't really make any effort to optimize it (I confess I got a bit lazy and used a few globals), and I'm sure there are some scary parts. If anyone spots something truly evil, please let me know so I can avoid using that construct in the future. I tried to make my code a bit generic so I could apply it to other puzzles as well.

    According to this code, there are 2 solutions, each 112 moves in length (where 1 move is defined as moving 1 block exactly one square). Of course, there are many other solutions possible that use more than 112 moves. I am very pleased that the number of steps (112) agrees with previous solutions!

    Update: I should note that since the board has left-right symmetry, the "two solutions" are simply mirror images of each other. Thanks to tye for the reminder.

    My code:

    And the two solutions:

    Now I'm going to see how the other solutions work... :)

      According to this code, there are 2 solutions,

      There are dozens of solutions and you throw most of them away at intermediate steps because they resulted in equivalent board positions.

      But you didn't bother to throw away duplicates that are left-rigtht mirror images of each other despite the board being symmetrical that way. (Neither did I.)

      So your "two" solutions means that, when using the minimum number of simple moves, the board layout (considering as identical any peices that are of the same shape and orientation) right before the last move is unique except for left-right mirroring.

      - tye        

        I took the symmetry into account and I found only one solution at 112 moves. Using more moves, there are another 483 solutions:

        The longest solution takes 158 moves. Of course this is making sure that no configuration is visited more than once. If I solved it by hand I'm pretty sure I'd take more than 158 because I would go in circles... ;-)

        Quite true. I thought of the mirror-image issue and I was going to update the post noting the symmetry, but you beat me to it! I'll do that now...

        Thanks for the comment. My language was not as precise as it could have been.

Re: Challenge: Setting Sun Puzzle
by tilly (Archbishop) on Oct 04, 2004 at 16:01 UTC
    Define "move".

    If I slide 2 pieces over one, is that 2 moves (one for each piece) or 1?

      For the purpose of being clear and fair to anyone playing along at home, a "move" is defined by sliding a single piece, regardless of how far it slides. For instance, the small squares may be able to move twice their size but that only counts as a single move.

      Cheers - L~R

      Changed "until it stops" to "regardless of how far it slides"

        Can you turn corners, or would that count as two moves?


Re: Challenge: Setting Sun Puzzle
by Roy Johnson (Monsignor) on Oct 04, 2004 at 16:39 UTC
    There might be some ideas to be gleaned at Perl Golf, which had a contest to solve the similar Rush Hour puzzle. But the Perl Golf site is unresponsive at the moment.

    Caution: Contents may have been coded under pressure.
      Hmm, seems like a nice move engine and decision tree for me ... I'd do it, but then I'd hijack a huge chunk of work time -- and I did that on Friday :) This really should count as work though. Not enough people in corporate america even care about solving interesting problems or designing something really off the wall. It sucks.
      Mmm, there was a problem with the nameserver setup, fixed now. You can find the relevant golf (and solutions by following some links) here.
Re: Challenge: Setting Sun Puzzle
by Tii (Monk) on Oct 04, 2004 at 15:49 UTC
    Very neat challenge.

    As soon as I figure out how to represent the problem in perl, I'll give it a shot and post the solution if I come up with one. I've done similar problems in Prolog in school way back, but this would be my first try at a perl solution.

    I'm curious to see what other monks come up with as well.

Re: Challenge: Setting Sun Puzzle
by dragonchild (Archbishop) on Oct 04, 2004 at 17:27 UTC
    I don't solve the problem, but I have a framework for letting someone play the game. (It's simplistic, but it's something. I don't feel like coding up the search algorithm at work.)

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

Re: Challenge: Setting Sun Puzzle
by tall_man (Parson) on Oct 29, 2004 at 16:48 UTC
    Nobody attempted to find the optimum solution where "round-the-corner" and other two-step moves of a single piece are counted as one move. It's not the same thing as optimizing for one-step moves and then merging adjacent moves of the same piece. The 112 step solutions merge down to about 96 steps, but it can be done in 79. I have placed the solution on tall_man's scratchpad.

    The code I used to solve it is OCaml, but it could easily be converted to perl.

Re: Challenge: Setting Sun Puzzle
by ggg (Scribe) on Nov 23, 2004 at 22:33 UTC
    If you approach this problem the way Alexander the Great approached the Gordian Knot, it can be solved in one move:
    rotate the puzzle 180 degrees.

    Not very perlish, though. ;-)