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



Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Edgematching problem - looking for help
PostPosted: Sat Aug 10, 2013 6:22 pm 
Offline

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
 Profile  
 
 Post subject: Re: Edgematching problem - looking for help
PostPosted: Sun Aug 11, 2013 11:56 am 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: Edgematching problem - looking for help
PostPosted: Sun Aug 11, 2013 12:47 pm 
Offline

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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 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 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