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

TwistyPuzzles.com Forum
 It is currently Fri Jul 25, 2014 11:14 am

 All times are UTC - 5 hours

 Page 1 of 1 [ 4 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: David Parlett's Puzzle of Oz - how many solutions are there?Posted: Fri Sep 13, 2013 10:12 am

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

 Post subject: Re: David Parlett's Puzzle of Oz - how many solutions are thPosted: Sat Sep 14, 2013 1:17 am

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

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

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

 Post subject: Re: David Parlett's Puzzle of Oz - how many solutions are thPosted: Tue Sep 17, 2013 7:34 pm

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 4 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: mixer and 6 guests

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

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic