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

TwistyPuzzles.com Forum

It is currently Fri Apr 18, 2014 4:50 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 31 posts ] 
Author Message
 Post subject: Untouchable 11 - Master Challenge
PostPosted: Tue Mar 27, 2012 9:15 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
All,

TomZ has mentioned Gathering for Gardner already so I thought I'd go ahead and share my gift exchange puzzle for the conference.

Image

Untouchable 11 - Master Challenge is a hexomino packing puzzle based on the original Untouchable 11 puzzle you can play here.

http://www.smart-kit.com/games/untouchable-11/

The goal is to place all 11 hexominos on the board such that none of them touch even at a corner. The hardest version of the original puzzle has 7 solutions. This puzzle only has 2 solutions.

VIDEO

You can purchase this in my shapeways shop.
http://www.shapeways.com/model/487355/

And I'm working with Peter Grabarchuk, the creator of the original puzzle, to get a playable app made so that is on the way as well.

Here is the paper for G4G10.
http://wwwmwww.com/Puzzle/G4G10/U11MasterChallenge4.pdf
I was also asked to make a profile for myself so I thought I'd go ahead and share that here as well.
http://wwwmwww.com/Puzzle/G4G10/CarlHoffProfile.pdf

I'm very proud of this puzzle and I'm wanting to make it available for a reasonable cost. To dye each piece a different color I ended up spending $25 on Rit Dye. So if there are 10 or more people interested in this I'm willing to dye all sets at once and sell a finished dyed puzzle for $30 plus shipping to you. If there is interest I'll start a list here. [EDIT] List has been started below.

This is also the puzzle I hinted at here.

And I'm also wanting to offer a prize to the first person to email me a picture of a solution. So I'll offer a free Doctor Cube to the first solver as determined by the time stamp of their email to my gmail address (it shouldn't be too hard to find my address). If no one has solved it before the end of April I'll offer the first solver a choice of a Doctor Cube or a Doctor Skewb. The only request that I make is that no one post a picture of the solution on line. That to me would take all the fun out of it. I'm aware of maybe a dozen or so that have solved the original puzzle by hand. I spent my free time over 3 or 4 weeks trying to solve it and then resorted to writing a program that itself took over a month to solve it. That was writen in quick basic 4.5 so it certainly wasn't the fastest software solution but I would really ask they you make a serious effort to solve this my hand before resorting to writing code to solve it for you.

For the 2nd and 3rd people to email me a solution (provided the solutions isn't leaked) I'm willing of offer them the option to purchase a Doctor Cube or a Doctor Skewb from Shapeways with no markup.

You do NOT need to purchase the Shapeways model of Untouchable 11 - Master Challenge to play, though it would certainly be appreciated. You can print out the above PDF and cut out the pieces or you could wait for the app to get finished and then once solved email me a screen capture.

Have fun, I hope you enjoy this as much as I enjoyed the original Untouchable 11,
Carl

People interested in a dyed finished puzzle:
(1) bmenrigh
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)

_________________
-
Image

Image


Last edited by wwwmwww on Wed Mar 28, 2012 5:18 am, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Wed Mar 28, 2012 3:54 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Carl this search space is HUGE. Even with some pruning tricks it is massive. This isn't a contest over who wrote the program the fastest, this is a contest over who has the fastest computer.

Or somebody could come along with a smart algorithm and win it without a fast computer. Seems unlikey though.

Sign me up for a copy should 9 others want one too :-)

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Wed Mar 28, 2012 6:09 am 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
bmenrigh wrote:
Carl this search space is HUGE. Even with some pruning tricks it is massive. This isn't a contest over who wrote the program the fastest, this is a contest over who has the fastest computer.
I hate to disagree and I really can't say all I want to say on this topic without giving too much away. But I've been aware of G4G10 for less then two months and in that time I've searched the complete seach space of 300+ different 11 pieces subsets of the hexominos to find this puzzle and I'm still searching to see if I can find a set with a single solution. Back in early 2009, I was aware of a program that could perform a complete search of the original Untouchable 11 puzzle in 45 minutes and it I'm sure would solve this one just as fast if I had a way to change the piece definitions. The program I'm using today typically takes between 2 and 4 hours for most sets and the ones with more solutions take longer as they don't run into dead ends as fast. Maybe after this is solved (or everyone gives up) I'll say more but there are already "hints" out there on how to solve this type of problem very fast if you want to use a PC.

Now having said that, the hints I'm refering to have been out there for years, and even today most that solve the Untouchable 11 puzzle have done so by hand. To be honest, I may be the only solver that has resorted to using a PC. Peter Grabarchuk who make the original puzzle did so by hand without the aid of a computer. I find that amazing. I spent weeks trying to solve it by hand and I knew it was solvable. I can't imagine trying to solve that puzzle by hand if you didn't even know it had a solution. So I'd highly recommend the original Untouchable 11 as a good stepping stone to this puzzle. Start with the easy version of that puzzle (the 9×17 board) which you should be able to solve by hand rather easily. Here is some data from that puzzle.

hard.txt (1,878 bytes)
7 solutions
201781800045 pieces tried
3984.57 seconds ~ 1.11 hours
solution density = hard

medium.txt (99,280,684 bytes)
482482 solutions
7624444667844 pieces tried
159415 seconds ~ 1.85 days
solution density = medium ~ 1824*hard

easy.txt (13,747,298,753 bytes)
65516235 solutions
52247612315783 pieces tried
1.19402e+006 seconds ~ 13.8 days
solution density = easy ~ 19.82*medium ~ 36150*hard

And note the program I used to get this data took 2 weeks to perform a complete seach of the easy puzzle and only a bit over an hour to search the hard puzzle. And I also want to point out that it is possible to solve the original puzzle using a 9×16 board. And that makes a very nice stepping stone between the medium and hard puzzle. Play on the 9×17 board, just don’t use the last row.

So back to the search space being HUGE. I'd say its all relative. The size of the search space of the easy version of the original Untouchable 11 is much much bigger then the hard puzzle. Yet it should be solvable by most here by hand that are willing to give it 20 or 30 minutes of their time. And in comparison to the Eternity Puzzle:

http://mathworld.wolfram.com/Eternity.html

the search space is a grain of sand where for Eternity it might be all the grains of sand on the planet. Today the complete search space of Untouchable 11 can be searched in under an hour. I don't think I've even seen an estimate for that figure for Eternity but if I had to guess I wouldn't be surprised that it was on the order of the age of the universe or even longer.

And with the comparision to Eternity, I want to add that Christopher Monckton's idea beind Eternity was to make a puzzle which was just as likely to be solved by hand as it was by computer. He was wrong and the main reason he was wrong was he had no idea how many solutions the puzzle had. So I think this challange is much more suited to being a fair challange between PC and human. Sure a PC can solve it and fairly fast after things have been optimized. But going back to my experience with Untouchable 11 and more or less giving up after finding many near solutions (states where just 2 pieces touched at a corner or states where the last piece would fit if it were just a different hexomino) I sat down to write a program. That took weeks. And that program took about a month to run as I certainly wasn't an expert in making these types of programs then. So after seeing the solutions and comparing them to some of my near solutions I realized I was far closer to a solution that I ever guessed. I have no doubt that if I had stuck with it a bit longer I could have solved it by hand too and I suspect I would have had a solution far faster. I certainly learned alot more by writing the program but a part of me is sad I gave up trying to solve it by hand when I did. And unlike Christopher Monckton's approach where he tried to even the odds between human and computer by making the odds of finding a solution basically equal to zero by either hand or computer I'm just trying to push the solve time by hand up to the amout of time it would take to write, debug, and run your own program. I really don't expect the PC's speed to be a factor.

Carl

P.S. That Eternity link above mentions a harder puzzle is possible using a smaller number (about 140 pieces) of 12-polydrafters. Anyone know the 140 piece puzzle this is talking about? I'd be curious to see a picture.

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Wed Mar 28, 2012 8:08 am 
Offline
User avatar

Joined: Wed Apr 13, 2011 8:37 am
Location: Germany
Hi everybody,

18 years ago I made a wooden puzzle. These are planar pentominoes with cubes.
I wrote a java program that shows solutions of these kind of puzzles. (Badlam Cube, Somacube).

In the program you can click "+" & "-" to show every piece. The program can save the solution as an animated gif.
The program calculates the solutions from different piece-sets and different figures. You can expand the zip and doubleclick the jar file.
The bottom picture is generated with this program.

Attachment:
pentoblock.jpg
pentoblock.jpg [ 120.73 KiB | Viewed 4543 times ]

Attachment:
pyramid.gif
pyramid.gif [ 21.59 KiB | Viewed 4543 times ]


Attachments:
pentomino.zip [17.35 KiB]
Downloaded 95 times
Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Wed Mar 28, 2012 3:12 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Carl you must have a more efficient algorithm than me. My program does the obvious dead-end short-circuiting but it isn't enough. It'll be weeks at the rate it's going.

I suspect my program is at least 1000x times as fast at executing as yours too since I wrote it in C and threaded it across 8 cores.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Fri Mar 30, 2012 3:29 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I now have both solutions :D . My program exhausts the search space in about 5 hours.

A few comments:

The obvious recursive algorithm will work and the search space is absurdly huge. If you just prune the obvious dead ends you won't be pruning enough. You have to be very innovative in the pruning algorithm. There is a representation of the puzzle that is slightly easier to prune than the most obvious way to do it.

Furthermore, the depth in the recursion that you are able to prune matters. A minor improvement in the pruning algorithm will have a linear improvement in the average depth you prune but because the recursion grows exponentially, linear improvements save work exponentially. It is worthwhile to spend a lot of computational time on pruning in order to save work.

There are still some additional improvements I can make to the pruning algorithm. It is entirely possible that I will be able to get the existing program to find both solutions in an hour. Once I have optimized the pruning algorithm I'll worry about an optimized implementation.


EDIT:

It's wrong of me to take all the credit for this program. There has been a huge amount of brain storming going on in the IRC channel and I got a great deal of help from GuiltyBystander, Daniel Kwan, and Eric Vergo.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Last edited by Brandon Enright on Fri Mar 30, 2012 4:41 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Fri Mar 30, 2012 4:25 pm 
Offline
User avatar

Joined: Wed Dec 14, 2011 12:25 pm
Location: Finland
Congratulations on cracking it! I tried to do it by hand but only got a situation several times where just two pieces would touch each other by a corner.

So now that the spell is broken (isn't it?), I'd like to ask something regarding the two solutions: are they completely different or do they differ only by some subgroup of pieces being oriented differently? Meaning this:
Attachment:
untouchable11.png
untouchable11.png [ 8.57 KiB | Viewed 4320 times ]

These two pieces could be rotated 180 degrees still occupying the same shape. So do the two solutions arise because of these kinds of groups or are the two solutions completely different?

_________________
My pen-and-paper puzzles


Last edited by Coaster1235 on Fri Mar 30, 2012 4:45 pm, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Fri Mar 30, 2012 4:38 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Coaster1235 wrote:
Congratulations on cracking it! I tried to do it by hand but only got a situation several times where just two pieces would touch each other by a corner.

So now that the spell is broken (isn't it?), I'd like to ask something regarding the two solutions: are they completely different or do they differ only by some subgroup of pieces being oriented differently? Meaning this:
Attachment:
untouchable11.png

These two pieces could be rotates 180 degrees still occupying the same shape. So do the two solutions arise because of these or are they completely different?
The solutions are unique -- that is -- they are different under all obvious transformations. Because the board is a square and pieces can be flipped upside down and rotated each solution comes in 8 forms. Further, if you somehow stickered the pieces so that their orientations and sides were all unique then the pieces that have mirror or rotational symmetry would also be able to vary.

I expected the solutions to be very similar. They are but they differ in an unexpected (to me) way.

Imagine a solution where all 11 pieces are placed. The second solution requires that you do do three swaps (allowing for orientations to change during swap). (AB)(CD)(EF) in cycle notation. The other 5 pieces stay the same.

Your example is interesting :wink: .

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Sat Mar 31, 2012 1:06 am 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
This was a lot of fun. My code finally found the 2 solutions. It'll be a few more hours/days before it completely exhausts the search space.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Mon Apr 02, 2012 6:54 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
The Doctor Cube has been won. There have been 2 to find a solution so far but the first passed on the prize. So both the 2nd and 3rd prizes are still available. I also still have bmenrigh listed as the only one interested in a dyed physical puzzle. If anyone else is interested please let me know.

And the app is in testing now so I hope to have it up soon.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Mon Apr 02, 2012 7:04 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
bmenrigh wrote:
I expected the solutions to be very similar. They are but they differ in an unexpected (to me) way.

Imagine a solution where all 11 pieces are placed. The second solution requires that you do do three swaps (allowing for orientations to change during swap). (AB)(CD)(EF) in cycle notation. The other 5 pieces stay the same.

Your example is interesting :wink: .
I don't have the solutions in front of me at the moment, but your statement sounds odd to me. As I recall the set of 5 pieces (or 6 pieces depending on how you looked at it) could be flipped and/or rotated as a whole to allow one to get the second solution from the first in a manor very very similiar to what Coaster1235 showed with his example. I don't think your statement is wrong... just very oddly worded and maybe that was intentional... not sure.

Carl

_________________
-
Image

Image


Last edited by wwwmwww on Mon Apr 02, 2012 7:58 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Mon Apr 02, 2012 7:14 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
I'm a little late to the game here, but I see discussion of search algorithms for this problem and no mention of Donald Knuth's dancing links algorithm, so something is wrong!

Anyone who wants to program something like that, this is required reading.

Edit -- did nobody try using BurrTools for this? It uses dancing links. The way you would represent this problem for BurrTools is to use a half-size grid, and pad each piece with a layer of the smaller grid units. Also pad the box with an extra layer. That effectively keeps the original pieces from touching, even at a corner. The one problem with this approach is that BurrTools could find solutions with pieces placed on the smaller grid, but not aligned on the original grid. Those would have to be removed by hand, assuming there weren't too many to begin with. I'm not a heavy BurrTools user; I prefer to write my own code for interesting search problems. But this one seems like an obvious BurrTools candidate.


Last edited by bhearn on Mon Apr 02, 2012 7:25 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Mon Apr 02, 2012 7:24 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
wwwmwww wrote:
]I don't have the solutions in front of me at the moment, but your statement sounds odd to me. As I recall the set of 5 pieces (or 6 pieces depending on how you looked at it) could be flipped and/or rotated as a whole to allow one to get the second solution from the first in a manor very very similiar to what Coaster1235 showed with his example.[...]
Well I'm trying to be somewhat vague but the way I see the two solutions, they share 5 pieces in the same spot and orientation. The remaining 6 pieces are in three pairs and each pair swaps (and undergo some rotation).

Coaster1235's example of two pieces being right next to each other is a simple example of what is happening. The way I see the pieces, the first solution would be written linearly as:

A B C D E F M N O P Q.

The second solution would be:

F E D C B A M N O P Q

Where the cycles were (AF)(BE)(CD)(M)(N)(O)(P)(Q)

There isn't one pair that has the ability to "flip" but rather the interaction of 3 pairs that together can swap and still fit against the group of the other 5 pieces.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Mon Apr 02, 2012 7:49 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
bhearn wrote:
The way you would represent this problem for BurrTools is to use a half-size grid, and pad each piece with a layer of the smaller grid units. Also pad the box with an extra layer. That effectively keeps the original pieces from touching, even at a corner. The one problem with this approach is that BurrTools could find solutions with pieces placed on the smaller grid, but not aligned on the original grid. Those would have to be removed by hand, assuming there weren't too many to begin with. I'm not a heavy BurrTools user; I prefer to write my own code for interesting search problems. But this one seems like an obvious BurrTools candidate.
I've not used BurrTools but from what you have said I believe its safe to say that your "way to represent this problem" isn't the best way. There is another way which avoids your "not aligned" solutions automatically and I would also guess be much faster. ;)

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Mon Apr 02, 2012 7:57 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
bhearn wrote:
Edit -- did nobody try using BurrTools for this? It uses dancing links. The way you would represent this problem for BurrTools is to use a half-size grid, and pad each piece with a layer of the smaller grid units. Also pad the box with an extra layer. That effectively keeps the original pieces from touching, even at a corner. The one problem with this approach is that BurrTools could find solutions with pieces placed on the smaller grid, but not aligned on the original grid. Those would have to be removed by hand, assuming there weren't too many to begin with. I'm not a heavy BurrTools user; I prefer to write my own code for interesting search problems. But this one seems like an obvious BurrTools candidate.
I was not aware of BurrTools or the Dancing Link datastructure / algorithm. I just read most of Knuth's paper and he drops some pretty big hints that took GuiltyBystander and I a few days to come up with.

I ended up writing my own code in C. I then "vectorized" it by expressing rows of the board as bits in an integer. You can check for fit or "place" a piece on the board with bitops rather than working via nested loops in a matrix.

The way I setup the backtracking (via recursion) is a bit different than some other polyomino solving solutions. Knuth points out why you shouldn't do what I did :oops: .

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Mon Apr 02, 2012 8:04 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
wwwmwww wrote:
I've not used BurrTools but from what you have said I believe its safe to say that your "way to represent this problem" isn't the best way. There is another way which avoids your "not aligned" solutions automatically and I would also guess be much faster. ;)

Carl

I just set it up -- it looks like a better way is to use BurrTools' notion of variable voxels. I'm not a BurrTools expert, so I don't really know what I'm doing, but I think I've now set it up correctly. It's been running for 5 minutes; no solution yet. I have to say, I'm a little disappointed in its speed; it's only hit about 900,000 assemblies so far. I'm sure a program written just for this problem could be much faster, but then I would have thought BurrTools would handle it with no problem. It's possible I set it up wrong.

But if you haven't used BurrTools, maybe this isn't what you meant... what did you have in mind?

Edit -- no, I'm an idiot, variable voxels don't do what I imagined they did. My setup should yield lots of false solutions, and BurrTools hasn't found any yet, so I must have set it up wrong.


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Mon Apr 02, 2012 10:12 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
bhearn wrote:
But if you haven't used BurrTools, maybe this isn't what you meant... what did you have in mind?
I'm not familiar with variable voxels so let me start by stating what it was that I thought you were doing. By stating you were using a half-size grid, I believed you were maping the problem of placing these 11 hexominos on a 12x12 grid to the problem of placing 11 "padded" pieces onto a 26x26 grid which itself can be viewed as a 24x24 grid "padded" with an extra layer all the way around. While that does work you can do the same thing without going all the way to the 26x26 grid. Ask yourself what the dual of a 12x12 grid looks like.

Carl

[edit] Corrected the 11x11 grid statement... I meant 12x12 grid.

_________________
-
Image

Image


Last edited by wwwmwww on Wed Apr 04, 2012 5:59 pm, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Mon Apr 02, 2012 11:02 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
wwwmwww wrote:
[...]By stating you were using a half-size grid, I believed you were maping the problem of placing these 11 hexominos on a 12x12 grid to the problem of placing 11 "padded" pieces onto a 26x26 grid which itself can be viewed as a 24x24 grid "padded" with an extra layer all the way around. While that does work you can do the same thing without going all the way to the 26x26 grid. Ask yourself what the dual of an 11x11 grid looks like.
I think you mean the dual of a 12x12x12 grid.

At first I programmed an "aura" around pieces (at the suggestion of DKwan) where the rule was aura could go on top of aura but pieces could not go on top of aura. This also gave me a pretty good measure of how much open area was left on the puzzle and allowed for a pretty decent pruning metric. I abandoned the metric for your dual idea because with you dual idea you can quantify the exact amount of "wasted space" in the grid. With an aura the wasted space depends on how much overlapping aura you have. Knowing now of the various bugs I had in the aura implimentation, I think if I went back and fixed them my aura representation would be only a few factor slower. Unfortunately having aura in a grid is not conducive to bit operations so vectorizing an aura-based implementation would be hard.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 2:20 am 
Offline
User avatar

Joined: Wed Dec 14, 2011 12:25 pm
Location: Finland
I tried using BurrTools - estimated time was over 3 months :lol:
And yes, I designed the pieces so that they couldn't touch each other. Probably horribly ineffectively, my board size was 38^2-12^2 (you can probably guess what I did).

_________________
My pen-and-paper puzzles


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 9:34 am 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
bmenrigh wrote:
I think you mean the dual of a 12x12x12 grid.
Yes, I did mean 12x12 grid. However I'm not sure how you bring the 3rd dimension into this.
bmenrigh wrote:
At first I programmed an "aura" around pieces (at the suggestion of DKwan) where the rule was aura could go on top of aura but pieces could not go on top of aura. This also gave me a pretty good measure of how much open area was left on the puzzle and allowed for a pretty decent pruning metric. I abandoned the metric for your dual idea because with you dual idea you can quantify the exact amount of "wasted space" in the grid. With an aura the wasted space depends on how much overlapping aura you have. Knowing now of the various bugs I had in the aura implimentation, I think if I went back and fixed them my aura representation would be only a few factor slower. Unfortunately having aura in a grid is not conducive to bit operations so vectorizing an aura-based implementation would be hard.
Great minds think alike. This "aura" method is exactly the same menthod my first program used to solve the original Untouchable 11 puzzle several years ago. Granted that program took a month to 6 weeks to complete its search as I recall.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 9:42 am 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Coaster1235 wrote:
Probably horribly ineffectively, my board size was 38^2-12^2 (you can probably guess what I did).
38^2-12^12 as in 1444x144? If so I actually don't have a clue what you did. How did the square board become a rectangle? I understand the 26x26 board approach as I was actually writing my second program to try and solve it that way when the dual approach dawned on me.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 10:52 am 
Offline
User avatar

Joined: Sat Jan 01, 2011 12:54 pm
Location: Copenhagen, Denmark
I think you should think of a 38x38 grid with 144 squares "strategically" removed to enforce alignment.

For what it's worth, I've been running BurrTools for the past few days with what I think is the "dual" approach you describe above. It's currently at 63% with no solutions found, and will require 1.1 days to finish (having already run for 2 days, although I started it closer to 4 days ago). Unfortunately, I'm running it on a laptop, so I can only keep it running when I have more than just battery power. Hopefully I've input everything correctly. My solution grid is 13x13.

--Taus


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 12:10 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Taus wrote:
I think you should think of a 38x38 grid with 144 squares "strategically" removed to enforce alignment.

Ahh... I see now. That is a rather creative mapping of the problem that I haven't thought of before. It should certainly work, but as he realized, I'm sure its far from the most efficient. Still its a very interesting approach to the problem.

By the way, is no one trying to solve this problem by hand? I'm pretty sure it should be doable, though I'm sure that will be easier after the app is available.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 12:43 pm 
Offline
User avatar

Joined: Wed Dec 14, 2011 12:25 pm
Location: Finland
wwwmwww wrote:
Ahh... I see now. That is a rather creative mapping of the problem that I haven't thought of before. It should certainly work, but as he realized, I'm sure its far from the most efficient. Still its a very interesting approach to the problem.

By the way, is no one trying to solve this problem by hand? I'm pretty sure it should be doable, though I'm sure that will be easier after the app is available.

Carl


One of the pieces would look like this:
Attachment:
untouchablepiece.png
untouchablepiece.png [ 10.1 KiB | Viewed 3958 times ]

And the board was, as Taus explained, a 38*38 grid with pegs removed. I can only imagine the horror that BurrTools had to go through, having to try so many placements that wouldn't work anyways :lol:

I did try the problem by hand as I said earlier. I got a few almost-solutions (two pieces still touching by a corner). I can post one here if it's ok?

EDIT:
Attachment:
untouchabl11.jpg
untouchabl11.jpg [ 75.93 KiB | Viewed 3943 times ]

_________________
My pen-and-paper puzzles


Last edited by Coaster1235 on Tue Apr 03, 2012 1:26 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 1:06 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Coaster1235 wrote:
One of the pieces would look like this:
Yes, I had figured that out. Its a rather creative solution to make sure the pieces don't touch and still remain on the original grid. I like that aspect of it. But I'm sure your solver didn't like it very much as you found out. :lol:
Coaster1235 wrote:
I did try the problem by hand as I said earlier. I got a few almost-solutions (two pieces still touching by a corner). I can post one here it it's ok?
Yes, you can post one if you like. Let's not post too many. When I was solving the original Untouchable 11 puzzle I had saved my near solutions too and then once I had the solutions in hand I could see ways I should have been able to jump from a few of my near solutions to an actually solution. Its always much much easier with hindsight and knowing where you need to go but I like to think I could have solved the original puzzle by hand had I not given up when I did.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 1:33 pm 
Offline
User avatar

Joined: Wed Dec 14, 2011 12:25 pm
Location: Finland
Picture edited to prev. post. I also think I got the trick that Taus (and others) used to have such a delightfully small grid... why didn't I think of that?
One of the pieces would look like this, am I right? I set BurrTools to search for solutions... "only" 2.8 days to go :D
Attachment:
untouchab11.png
untouchab11.png [ 3 KiB | Viewed 3941 times ]

_________________
My pen-and-paper puzzles


Last edited by Coaster1235 on Tue Apr 03, 2012 11:30 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 5:06 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Coaster1235 wrote:
Picture edited to prev. post.
Very pretty. May I ask where you got your pieces? I almost like your set more then then one I had made on Shapeways. It certainly looks cleaner. The only plus I can think of about my set is I made the shapes such that they enforce the rules and they can't touch and still fit in the grid.
Coaster1235 wrote:
I also think I got the trick that Taus used to have such a delightfully small grid...
Yes, and Taus wasn't the first. I posted about the details of that transformation back on March 23, 2009 and that description is still on line (can you find it?). In my second post in this thread I stated... there are already "hints" out there on how to solve this type of problem... and that was one of them. Though I tend to doubt that I was the first use this type of transformation myself.

Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 5:26 pm 
Offline
User avatar

Joined: Wed Dec 10, 2008 6:26 pm
Location: Boston area
I tried (and failed so far) to solve the puzzle by hand, but I sure wish I had thought of the ingenious idea of using the pieces from the Blokus game! That would have been much easier than cutting out and trying to manipulate tiny pieces of paper. I even have Blokus sitting right in my living room. D'oh! I'll have to give it another go using those parts, although I like very much the way Carl designed the puzzle to make sure the rules are followed.

EDIT: Wait a minute! Blokus pieces only go up to a maximum of five squares, not the full six required for this puzzle. That won't make it nearly so easy to use the Blokus parts as care will need to be taken to keep each part together properly.

_________________
Visit Pitcher Puzzles where you can buy the IPP award-winning RotoPrism 2, Fracture-10, and many, many more.


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Tue Apr 03, 2012 11:37 pm 
Offline
User avatar

Joined: Wed Dec 14, 2011 12:25 pm
Location: Finland
wwwmwww wrote:
Very pretty. May I ask where you got your pieces? I almost like your set more then then one I had made on Shapeways. It certainly looks cleaner. The only plus I can think of about my set is I made the shapes such that they enforce the rules and they can't touch and still fit in the grid.

Carl

David Pitcher wrote:
I tried (and failed so far) to solve the puzzle by hand, but I sure wish I had thought of the ingenious idea of using the pieces from the Blokus game! That would have been much easier than cutting out and trying to manipulate tiny pieces of paper. I even have Blokus sitting right in my living room. D'oh! I'll have to give it another go using those parts, although I like very much the way Carl designed the puzzle to make sure the rules are followed.

EDIT: Wait a minute! Blokus pieces only go up to a maximum of five squares, not the full six required for this puzzle. That won't make it nearly so easy to use the Blokus parts as care will need to be taken to keep each part together properly.

Yep, those are Blokus pieces. I just taped them together :D (though they don't want to sit in place as nicely with tape)

BurrTools just showed me the two solutions (took only 10 hours, it hasn't exhausted even half of the search space) and I think I actually was pretty close to the solution at some points, I just clinged too tightly to some pieces' positions... also the relationship between the two solutions did surprise me. I wouldn't work it quite like bmenrigh did...

_________________
My pen-and-paper puzzles


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Wed Apr 04, 2012 3:53 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
wwwmwww wrote:
While that does work you can do the same thing without going all the way to the 26x26 grid. Ask yourself what the dual of an 12x12 grid looks like.

Ah, yeah, I feel silly. That's a much better representation.


Top
 Profile  
 
 Post subject: Re: Untouchable 11 - Master Challenge
PostPosted: Thu Apr 05, 2012 6:07 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Untouchable 11 - Master Challenge is now live. Here is the direct link:

http://puzzles.com/PuzzleClub/Untouchable11MasterChallenge/index.htm

And its being advertized on their home page at the moment:

http://puzzles.com/

Enjoy,
Carl

_________________
-
Image

Image


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