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

TwistyPuzzles.com Forum
 It is currently Fri Jul 25, 2014 7:12 am

 All times are UTC - 5 hours

 Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Edgematching problem - looking for helpPosted: Sat Aug 10, 2013 6:22 pm

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Say you want to distribute four different colors around the edges of a kite quadrilateral. If we count reflections as distinct (i.e. if we have one-sided pieces) there are exactly 24 combinations.

Can these 24 edge-colored kites be placed on the faces of a deltoidal icositetrahedron such that colors match where edges touch?

I proposed this problem to Jaap recently, who ran it through a solver of his. It couldn't find any solutions. But he couldn't easily prove that none exist, either, and conceded it was possible the program also had an error.

Top

 Post subject: Re: Edgematching problem - looking for helpPosted: Sun Aug 11, 2013 11:56 am

Joined: Sat Jan 01, 2011 12:54 pm
Location: Copenhagen, Denmark
Here's a solution, assuming I haven't misunderstood anything (or made a mistake of some kind):

Code:
+-0-+-0-+
|   |   |
2   3   1
|   |   |
+-1-+-2-+
|   |   |
3   0   1
|   |   |
+-2-+-3-+-2-+-3-+-1-+-1-+
|   |   |   |   |   |   |
3   1   0   1   2   0   2
|   |   |   |   |   |   |
+-0-+-2-+-3-+-0-+-3-+-3-+
|   |   |   |   |   |   |
3   1   0   2   1   2   1
|   |   |   |   |   |   |
+-2-+-3-+-1-+-3-+-0-+-0-+
|   |   |
3   2   0
|   |   |
+-0-+-1-+
|   |   |
2   3   0
|   |   |
+-1-+-2-+
|   |   |
3   0   1
|   |   |
+-2-+-3-+
|   |   |
3   1   2
|   |   |
+-0-+-0-+

(To read this diagram, think of the polyhedron as a deformed cube where each face has been divided into four squares. Numbers 0 through 3 on the edges indicate colours.)

I solved this by encoding it (rather naively) as a constraint satisfaction problem which was then automatically transformed into a boolean satisfiability (a.k.a. SAT) problem. Transforming from CSP to SAT took roughly 8 seconds and solving the resulting SAT problem took only half a second. Making the ASCII-art diagram and hand checking the solution took much longer!

Enjoy!

\Taus

Top

 Post subject: Re: Edgematching problem - looking for helpPosted: Sun Aug 11, 2013 12:47 pm

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Thanks very much! I just double-checked it myself and it works out. I had a feeling it was possible!

Top

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

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: Google Adsense [Bot] and 4 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

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