## Untouchable 11: An online visual-spatial puzzle contest

**A list of people who have solved so far:**

* Hard: *Dan, Shawn, michaelC, LaDana, someone,Tumeke, Seelesscacti, Carl H., Bilbao, Suineg, Anka, EddB, Jerrud Edwin, MeetVikas

* Very Hard:* michaelc, Bilbao, Tumeke, Seelesscacti, Carl H., EddB, someone, Suineg, Shawn, Jerrud Edwin

** Impossibly Hard: **someone, Carl H. (

*Carl has also done some great analysis, please read in the comment section below*), Suineg, and Jerrud Edwin

‘someone’ is the 1st to solve all 3. He emailed and let me know he is a 17 year old high school senior who’s also taking courses at a local college in Computer Organization and Architecture. Interestingly, he was home-schooled until 7th grade. His parents tell him that he taught himself math before he could read or write. He is considered the top math student at his high school, and has participated in numerous math contests.

———————

Here’s a really neat (and hard!) new puzzle game made for Smartkit by Peter Grabarchuk. There are actually 3 challenges, and all are quite tough. We’ve got a Smartkit T-shirt and Puzzle Express 3 book (courtesy of Peter) to the first person who solves all 3 puzzles (send us a screen shot info@smart-kit.com). However, we’ll also keep and publish a list of all the uber-brains who manage to solve these.

Interestingly, all the Grabarchuk’s are into puzzles. Peter’s dad runs Ageofpuzzles.com, and Peter’s brother, Serhiy, Jr., has his website at UniPuzzle.com

*Give the Untouchable 11 online puzzle a try now!*

If you’re looking for a more relaxed puzzle game to try, check out Smart-Kit’s great jigsaw puzzles online. These jigsaws feature a very large playing field, with very high quality puzzle piece cuts. If you’re looking for something more educational for students, be sure to check out our very nice bridge building game, or perhaps this cool and very fun kids science game! If you’re trying to sharpen your mind and make your brain smarter, check out Smart-Kit’s huge selection of fun brain games.

Tommy| Profile October 23rd, 2008 - 2:20 pm4 is to tetris as 6 is to hexis

Untouchable » puzzlinks.com| Guest October 23rd, 2008 - 5:27 pm[…] is a new puzzle up at Smartkit called Untouchable that was written by Peter Grabarchuk. The goal is to arrange a group of hexominoes in a grid so […]

RK| Founder | Profile October 23rd, 2008 - 11:34 pmjust to update, no solutions submitted yet…

suineg| PUZZLE MASTER | Profile October 24th, 2008 - 6:07 pmman, the hard should be call impossible, jajaja, I am triying but I need some rest cool game, very very hard!!!

Someone| Profile October 24th, 2008 - 8:56 pmWoohoo! I solved it. Man that was hard. I was starting to think it was impossible.

michaelc| Profile October 24th, 2008 - 11:38 pmPretty tough it is. I almost got the last one, but one little corner!!!

RK| Founder | Profile October 25th, 2008 - 2:26 pm‘someone’ is the 1st to solve all 3, see updated post above

LeeJH| Profile October 27th, 2008 - 1:37 pmThis is *so* similar to the (somewhat easier!) game I’ve just written… http://discussionator.com/unify.html

suineg| PUZZLE MASTER | Profile October 28th, 2008 - 12:41 pmthe impossible version(hard) is really the hardest visual puzzle I had seen in my whole life, I have tried at least 6 hours and no solution has come to my head but I know something for sure is not a symmetrical solution because it always miss a corner, by the way congrats to ‘someone’

michaelc| Profile October 29th, 2008 - 5:23 pmThe last challenge is a 12×12. We have 11 pieces with 10 pieces being basically a 3×4 shape, and one shape being a 2×5 shape.

My general strategy was to put 4 of the 3×4 shapes into the top and 4 into the bottom of the 12×12 grid. Turn the corners toward the middle where there will be some holes for the last 3 pieces, as there is only “2” rows left.

And this works for me, except one little corner.

Now I’ve realized this will take more time for me to solve than I’m willing to give for it!

Nevertheless, I’d like to see the solution when everyone’s finished hacking their brains on it…

Shawn| PUZZLE GRANDMASTER | Profile October 30th, 2008 - 7:26 amSame problems with me. I have spent WAY too much time on the last puzzle! My strategy has been to minimize wasted space; if the placement of the first shape leaves 12 open spaces that could be filled without conflict, then they must all be used for this puzzle to work. So far, my best solution leaves one final piece to be placed in the middle, and I cannot avoid a corner-corner touch.

I am still looking for a pattern that might be better than mine at maximizing the number of blocks that border the edge of the puzzle. Minimizing open space at the edge should open up more space in the middle…

Carl H.| Profile December 13th, 2008 - 11:11 amWe start with ONE unit cube in THREE dimentions. The cube can be unfolded into TWO dimentions in ELEVEN ways. These eleven ways become the eleven pieces of the puzzle. So let’s examine these eleven pieces. They are a subset of the hexominos or the base SIX polyominos. FIVE of the pieces have EIGHT possible orientations. The other six have only FOUR orientations. NINE of the pieces need to be flipped in order to get all possible orientations. TEN of the pieces will fit into a three by four box. Only one requires a two by five box. Now that we are familiar with the pieces, the puzzle is to fit these eleven pieces into a TWELVE by twelve square such that none of the pieces touch each other, even at a corner. To solve this puzzle the numbers THIRTEEN and FOURTEEN proved very helpful (hint). So to recap, this paragraph currently contains all the numbers from one to fourteen except one and that is about to be fixed… as this puzzle has only SEVEN solutions, not counting rotations or reflections. And I sure had a blast finding those seven. THANK YOU!!!!

Some additional info:

The easy puzzle has 50,700 solutions.

The medium puzzle has 3,055 solutions.

The hard puzzle has 7 solutions.

Taking into account the size of the search space this makes the medium puzzle 18 times as hard as the easy puzzle and the hard puzzle 682 times as hard as the medium puzzle.

Enjoy,

Carl

suineg| PUZZLE MASTER | Profile December 13th, 2008 - 1:59 pmnice job Carl H, I have to confess, I am still a little bit lost even with that great analysis ( by a corner lost jajaj), I left this problem for a while but I am going to try to retake the solving and analysis, I tried with combination of rows like a matrix with 1 and 0 by combinatory mathemathics, adding each column and row so that the total of 1 add up to 66 (11×66) but took too long jajaja , anyone to solved this problem is really really good either at maths or visually, cool

michaelc| Profile December 14th, 2008 - 12:05 pmWow Carl H!

I have to say I’,m impressed.

How did you exhasut all possible solutions to the 3 puzzles?

I know of 3 ways one could tackle such an enormous task.

1.) Trial and error.

2.) Theoretical analyzing and coming up with a formula (very complicated I would think at least for my pea brain!).

3.) Computer solution doing trial and error method.

I would say if I were trying to count the number of solutions, I would try method #3 which I think would be my best bet at success. #1 method would take more than a lifetime to exhaust all possible solutions! The #2 method would burn my brain cells out I do believe!

Carl H.| Profile December 14th, 2008 - 1:44 pmThanks…

I solved the easy and medium puzzles by hand and played around with the hard version off and on for several days and always ended up with a corner touch at best. I had emailed to ask if the solution to the hard version was unique and was told they were aware of 2 solutions which told me the actual number of solutions was probably unknown. So at that point I had two puzzles I wanted to solve, the second being finding the total number of solutions as I was convinced it was small. To be honest I was just about convinced it was so small that this puzzle couldn’t have been made by hand. But I’ve since learned that Peter Grabarchuk solved this puzzle by hand when he first made it. I suspect that someone solved it by hand too. And I’m really impressed that is even possible considering the search space that was explored to find those 7 solutions involved 2,716,048,219 piece placements.

And yes I used a computer to explore all 3 puzzles using backtracking. Peter Knoppers explains the method here:

http://ce.et.tudelft.nl/~knop/puzzles.html

Though I think his pseudo code needs these 2 steps added between steps 11 and 12:

Increment shapeno to the next non-placed shape and set orientationno to 1

If shapeno is less than or equal to the total number of shapes then goto step 6

Note: shapeno can be incremented to the total number of shapes plus 1 if all the remaining pieces after the removed piece are already in the space.

I used Quick Basic 4.5 as it’s the only programing language that I know and this is the first program that I’ve writen in about a decade. I really need to learn something new as the last version of Quick Basic came out in 1988. Anyways, after writing the program and letting it run for a few days it became apparent that it would take the program months (maybe a year) to do a complete search.

Then one day while at lunch it dawned on me there was a much much easier way. I transformed this puzzle into another puzzle which was much easier to search with backtracking. I was also able to drop all my Quick Basic code (though I still have it running to verify that my program will find a solution) and used some free backtracking software that can be found on line and is super simple to use. I used that and it was able to do a complete search of all 3 puzzles at the same time in about 2 hours.

So I owe a great deal of thanks to the person that has made that code available. I’d name him here but that would probably give you guys too big of a hint.

Oh and I forgot to mention that in addition to the numbers 13 and 14, the number 15 was instrumental in the transformation too. I could show you how with a very very simple formual involving multiplication and subtraction but I’m afraid it would give too much away.

I just love the way this puzzle and these pieces seem to have such a direct relationship to the first 15 integers.

And not to turn those of you off too much that are trying to solve this puzzle by hand, I had saved a picture of what I considered by best attempt by hand. It had one corner touch and an open area that was 3×3. I could even remove the center piece that was causing the corner touch and put a second copy of one of the other pieces on without generating a corner touch. Looking at that near solution and the acutual solutions (which are all fairly closely related, six I’d call VERY closely related such that if you had one finding the other 5 by hand would be easy) I was much closer then I thought. So I certainly believe that Peter and someone solved this by hand.

suineg| PUZZLE MASTER | Profile December 14th, 2008 - 3:20 pmVery very nice, I think its really sincere of your part to told us you did the hard one by trial and error in a computer, but its not less amazing to program a code to give all the possible solutions, I think by computer and using and adding and subtracting by row and column so that the restrictions using linear programming will be possible giving the total adding to 66 and the maximun adding per row and per column, I have tried to solved this by hand and I came to three solutions where I was touching only by a corner, this was visually the hardest problems I have seen, even in the Peter and family site, cool but I will be back in the solving.

Carl H.| Profile December 15th, 2008 - 11:37 amUpdate:

Last friday I left all 3 searches running on my work PC and when I got in this morning I noticed it found more then the reported solutions for the easy and medium puzzles above. Still only 7 for the hard version. Digging a little deeper I then noticed that the hard solution was the only one that completed. The other two had stopped due to errors. I’m looking into it now but it appears that there are more than 50,700 solutions to the easy puzzle and more than 3,055 solutions to the medium puzzle. Once I figure out what the problem is I should be able to say more.

Carl

Caitlin.L| Profile December 26th, 2008 - 5:35 amI have managed to do the first two puzzles. The third puzzle is very hard. I keep getting one or two corners.

Carl H.| Profile January 20th, 2009 - 2:50 pmThe hard puzzle has 7 solutions. I’ve now verified that with 3 different programs. I’m still counting solutions for the easy and medium puzzles but while doing that I came across an interesting solution to the medium puzzle. Can you find it?

http://www.wwwmwww.com/U11/Medium2.png

The hard puzzle has 7 solutions and a search space of 2,716,048,219 piece placements. This puzzle has 1 solution and a search space of 269,067,576 piece placements. So even though it has fewer solutions its solution density is 1.442 times richer and thus this should be a little easier.

If this is still too hard, drop the restriction that the one piece can’t be flipped and you end up with a puzzle with 52 solutions and a search space of 458,511,640 piece placements. This produces a solution density over 44 times as rich as the hard puzzle so in principle it should be 44 times easier. This should still be harder then the medium puzzle by a fair bit but as I said I’m still counting solutions to the medium puzzle so I can’t give you exact numbers yet.

Anyways I thought I’d come up with a stepping stone that might help those that have solved the medium puzzle but are still working on the hard puzzle. I hope this serves that purpose.

Stay tuned,

Carl

Carl H.| Profile March 23rd, 2009 - 1:41 pmFinally….

I now have a program that can solve all 3 versions (easy, medium, and hard) thanks to Stefan W. It writes all the solutions to simple ascii files and here are the results:

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

We start with ONE unit cube in THREE dimensions. The cube can be unfolded into TWO dimensions in ELEVEN ways. These eleven ways become the eleven pieces of the puzzle. So let’s examine these eleven pieces. They are a subset of the hexominos or the base SIX polyominos. FIVE of the pieces have EIGHT possible orientations. The other six have only FOUR orientations. NINE of the pieces need to be flipped in order to get all possible orientations. TEN of the pieces will fit into a three by four box. Only one requires a two by five box. Now that we are familiar with the pieces, the puzzle is to fit these eleven pieces into a TWELVE by twelve square such that none of the pieces touch each other, even at a corner. To solve this puzzle I found it helpful to transform this puzzle into another. One involving fitting a subset of the base FOURTEEN polyominos and FIFTEEN monominos into a THIRTEEN by thirteen square. So to recap, this paragraph currently contains all the numbers from one to fifteen except one and that is about to be fixed… as this puzzle has only SEVEN solutions, not counting rotations or reflections.

This image helps to explain the transformation.

http://wwwmwww.com/U11/U11nodes.png

While this does help it isn’t necessary. I have one program that doesn’t make use of this transformation and it still can find all 7 solutions to the hard puzzle, it just takes much much longer.

By the way, it is possible to solve this puzzle using a 9×16 board. And that makes a much nicer stepping stone between the medium and hard puzzles then the puzzle I proposed in the post above. Play on the 9×17 board, just don’t use the last row.

Enjoy,

Carl

This puzzle will leave you… seeing stars | Smartkit Puzzles and Brain Teasers| Guest April 7th, 2009 - 7:55 pm[…] Someone (this 17 year old high school whiz was 1 of 2 to solve the ‘impossibly hard’ 3rd level of Untouchable11) […]

Jerrud Edwin| Profile September 22nd, 2009 - 2:42 pmI have finished the first two difficulty levels and am starting on the third, how can I get a screen shot saved once completed so I can send them in?

RK| Founder | Profile September 24th, 2009 - 8:51 amHi there Jerrud- good job on the 1st two levels. You can download a free screen grabber/capture tool to take the picture and then email it in to me info@smart-kit.com.

suineg| PUZZLE MASTER | Profile December 11th, 2009 - 11:01 amFinally done, 2 solutions only, but I dont see 6 similar like Carl H said it would, well I will keep looking for those 4

suropriya| Profile April 4th, 2011 - 11:53 pmhi i cant play u touchable 11 or any of the jigsaw games. what software shouls i have to play them? this is a great site..really the puzzles!!

Magic Links | Smart-Kit Puzzles and Games| Guest March 9th, 2012 - 9:09 pm[…] 3rd Update: Bharti, the wife of MeetVikas completed Magic Links too! MeetVikas solved the Hard Level of Untouchable 11. […]

Untouchable 11, Master Challenge! | Smart-Kit Puzzles and Games| Guest April 12th, 2012 - 10:40 pm[…] Challenge! [You can try the original Untouchable 11 & read the comments Carl & others left here] « Spring […]

Hamza| Profile June 12th, 2012 - 6:51 ami completed the puzzle but my name does not appear?

Jerrud Edwin| Profile December 19th, 2013 - 2:12 amThe solution to the 144 cell challenge was very surprising, now to see Carl’s master challenge! =-)