Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Tue Jul 22, 2014 6:39 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: David Parlett's Puzzle of Oz - how many solutions are there?
PostPosted: Fri Sep 13, 2013 10:12 am 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
The Puzzle of Oz is really more of a solitaire game, but it's quite a fun one.

It is played on a diamond-shaped board of 25 spaces:

Code:
...O...
..OOO..
.OOOOO.
OOOOOOO
.OOOOO.
..OOO..
...O...


25 pieces (5 each in 5 colors) are used. They are placed in a bag and drawn randomly.

To start, you draw four pieces and put them on the four corners in order. After that, continue to draw pieces, placing them on a space adjacent to any other piece, orthogonally or diagonally. However, pieces cannot be placed adjacent to other pieces of the same color. If you are able to place all 25 pieces, you win.

So, how many possible won boards are there? Not including rotations, reflections, or color-swaps (so say, two boards which are identical except that all the reds and blues were swapped, still only count as one solution).


Top
 Profile  
 
 Post subject: Re: David Parlett's Puzzle of Oz - how many solutions are th
PostPosted: Sat Sep 14, 2013 1:17 am 
Offline
User avatar

Joined: Wed Mar 15, 2000 9:11 pm
Location: Delft, the Netherlands
The program I use for solving edge-matching tiling problems can easily solve this kind of problem as well, but it does not reduce for symmetries. I can get it to reduce for colour permutation by the simple expedient of specifying the four colours that occur in some 2x2 area (those colours must necessarily differ).
This gives 172920 solutions.
Reducing for rotational/mirror symmetry, there are at least 172920/8 = 21615 solutions, the exact number probably being a bit more due to some positions being symmetric.

Here are two examples.
Code:
. . . 3 . . .
. . 1 2 1 . .
. 2 3 4 3 2 .
1 4 5 1 5 1 5
. 2 3 4 3 4 .
. . 5 2 5 . .
. . . 4 . . .


. . . 5 . . .
. . 1 2 3 . .
. 5 3 4 5 4 .
4 2 1 2 3 2 1
. 5 4 5 1 4 .
. . 3 2 3 . .
. . . 1 . . .

The 2x2 area at the top-left was fixed to 12/34. Under that condition, these two solutions are lexicographically the first and the last.

_________________
Jaap

Jaap's Puzzle Page:
http://www.jaapsch.net/puzzles/


Top
 Profile  
 
 Post subject: Re: David Parlett's Puzzle of Oz - how many solutions are th
PostPosted: Sat Sep 14, 2013 11:59 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Thanks Jaap! It's still a helpful result. :)

I do have one more question - if we use a variant set of pieces, identical except for each set of 5 same-colored tokens also being numbered from 1 to 5, and neither same-color or same-number pieces are allowed to be adjacent, how many solutions do we have there?


Top
 Profile  
 
 Post subject: Re: David Parlett's Puzzle of Oz - how many solutions are th
PostPosted: Tue Sep 17, 2013 7:34 pm 
Offline
User avatar

Joined: Wed Mar 15, 2000 9:11 pm
Location: Delft, the Netherlands
Jared wrote:
Thanks Jaap! It's still a helpful result. :)

I do have one more question - if we use a variant set of pieces, identical except for each set of 5 same-colored tokens also being numbered from 1 to 5, and neither same-color or same-number pieces are allowed to be adjacent, how many solutions do we have there?


This has 11992 solutions (reduced by colour permutations, and number permutations). Reducing this by rotation/mirror symmetry, you get at least 1499 unique solutions. There is a further symmetry of swapping the colours with the numbers, which would reduce it by another factor of 2, approximately.

Code:
            3,4
        1,1 2,2 1,3
    2,4 3,3 4,4 3,1 2,5
5,2 4,5 5,1 1,5 5,3 4,2 5,4
    1,4 2,3 3,2 2,1 3,5
        4,1 5,5 4,3
            1,2

            5,5
        1,1 2,2 3,1
    5,4 3,3 4,4 5,3 4,5
1,3 4,1 2,5 1,2 2,1 1,4 2,3
    5,2 3,4 4,3 3,5 4,2
        1,5 5,1 2,4
            3,2

_________________
Jaap

Jaap's Puzzle Page:
http://www.jaapsch.net/puzzles/


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group