Puzzle Description:

#1: Josh Greifer (joshgreifer) on Apr 5, 2010 [HINT] [SPOILER]

This puzzle has a unique solution, which can be solved using "domino logic".

Here's how to solve it:

Look at the nine columns that have a "3": Each of these 3's must always lie across a row with a 1. Therefore no two of these 3's can overlap by more than one square.

The nine columns containing a 3 will therefore need to be occupy all the rows, to avoid two of them both occupying a "1" row. In particular, one of the 3's will need to start at the top row. Only C19 can fit the bill, so R1C19-R3C19 are black.

This forces R1C17 and C18 to be black, and the remainder of R1, R2, C18 and C19 to be white.

Now the "domino logic" kicks in: Of the remaining 8 columns containing a 3, only C17 has a 3 that can be placed in R3.

..and so on

The puzzle is filled in this way, from the top right corner to the bottom left, with L-shaped chevrons.

This is kind of going too far. I'm not a fan of "domino" logic. Sorry.

great puzzle - this is what this web site should be for - hard puzzles, not those colourful crappy things with too many spaces filled in that there is no skill needed - this is a PUZZZZZZZZLE site, not a picture site.

Me encanto, la verdad es que aplicando simple logica se resuelve y ya entendiendo el sentido se va resolviendo solo, felicidades!

That part of my brain is just not working today. Instead of extended edge logic, I tried to imagine how it would fit together, like making a puzzle out of shapes. It was fun to see it solve that way, but it was not true logic, as I did not do any sort of "if, then" process, just totally visual.

Found to have a unique solution by jan.

Found to be logically solvable by jan.

Very clever little puzzle. It is definitely solvable, but it requires a holistic approach to the puzzle that is at odds with the usual method of just working with little bits at a time.

One of my little projects is continually updating a survey of computer programs that people have written to solve paint-by-number puzzles. (see http://webpbn.com/survey/) One of the ways I compare solvers is by testing them on a sample set of interesting puzzles from webobn.com. I've added this to that list of sample puzzles.

What initially attracted my interest is that my checker program was apparently unable to decide if it was unique or not. That's partly because on this site it is given a one second time limit to solve puzzles (I don't want it clogging up the web server for a long time). Without that time limit it takes 28 seconds to solve the puzzle and prove that it is unique. This is extremely long for a mere 19 by 19 puzzle. When I tested it on other people's solvers I found a wide range of results. Many require minutes to solve it. Some couldn't solve it in under half an hour. A few could do it in a couple seconds.
<p>
The problem, of course, is that computer programs are very rigid thinkers and excel at problems that can be solved by working on tiny bits of the problem at a time. Josh's solution for this puzzle is the opposite of that, requiring that you think about the entire puzzle all at once.
<p>
Another thing that interested me with this puzzle is that it is scalable. This one has nine little L-shapes (I called it "9-Dom" in the survey), but you could add more. You could make 10-Dom, 11-Dom and 1000-Dom. For a human solver who gets the trick, the size doesn't matter. All of them are equally solvable. But for a computer program that doesn't get the trick, it gets much harder as it gets larger. So a tempting thing to add to my survey would be a graph of run times for each solver on 3-Dom through 15-Dom. That might show something about how the search performance of the solver scales with puzzles size.

Another thing I like about this is that you could view the image as depicting a line of dominoes, so the logic and the image are both domino-like.

Josh: I'm wondering if you would be willing to give permission for this puzzle to be redistributed. This would mean that people who make solvers could include it in the test sets distributed with their solvers (with attribution) or it could be distributed as part of a package of test puzzles. This is kind of the moral equivalent of making it open source or placing it under a creative commons license.

I also notice that this puzzle is symmetric about a diagonal, but it's not immediately obvious to me that that would help us solve it, if we were willing to use symmetry as a solution technique, say if we knew a priori that the solution is unique. Is diagonal symmetry of any use at all?

Jan, I'm glad you appreciated this puzzle. Of course you can use it, I'd be flattered. This ability for humans to be able to do "..and so on..." -- i.e. inductive -- reasoning while most computer solvers can't is the reason why I created these puzzles. I like to show that people are still better than computers at certain problems -- and to stimulate programmers to create smarter programs. I'm slightly annoyed by brute-force game players and solver programs -- I've written a PBN solver myself too, which is nothing special -- just a big dumb backtracker (pretty fast though)

BTW I deliberately increased the size of some of these "domino logic" puzzles just to break the 1 second solve time of your checker!

I was first attracted to this site by your very interesting "Advanced Solving Techniques" page, and the different "logics" you identified there. This more humanistic way of approaching problems and puzzles and games has reaped rich rewards in a champion Gomoku playing program, where the language and terminology of expert Gomoku players has actually been coded into the program.

If I wanted to try and code inductive reasoning into a PBN solver I wouldn't know where to start really. I'd be very impressed if someone did it.


As to the holistic side, I agree it's also very hard to get a computer to do, but in this puzzle's case it's rather like the "summing" logic you describe in your Advanced Solving Techniques page.

The "colouring" techniques that Golomb used to prove theories about polyominos, are programmable -- I'm thinking of the most famous and simple example of checking whether you can use 31 dominoes to cover an 8X8 square with two opposite corners missing. A simple chessboard colouring of the square makes the answer obvious.

Thanks.

If you're interested in my survey, it's here: http://webpbn.com/survey/

If you want test data for your solver, or want me to test it against the others, I'm happy to do so. It's getting to be a pretty competitive business though.

I actually did the comparison of different solvers on variously scaled versions of this puzzle and wrote it up.

It's here: http://webpbn.com/survey/dom.html

I think this is a fun thing to put up as a challenge to designers of solvers.

I enjoyed this one, because the "aha!" came fairly quickly. If I hadn't found the solution right away, I would probably hate this puzzle. ;)

Dito #13.

I used to say "I don't like puzzles of nonsense image", but this puzzle demolished my theory and changed my way of thinking, because the kind of logic required to get the solution makes it a very good clever puzzle.

Here's a link to a PDF of an Australian research paper called "MDD Propogators with Explanation". On page 17 you'll see a picture of this puzzle. They can solve up to size 20, which is way better than I've seen anyone else do.

So this puzzle is now officially part of SCIENCE.

It's also an "Eyeball Bender" of a baseball.

Great puzzle! I'm still struggling to get beyond line logic and this one helped me a lot.

I'm sorry to say that I "intuited" the solution and solved in about a minute. This was obviously meant to be a fun and tricky solve but I just gave it a lucky guess.

I tried a "reductionist" approach. Row clues and column clues occur in repeating pairs (1; 3 1;) (1; 3 1), and likewise for the columns. So I suspected I could discard two adjacent rows and two adjacent columns from the middle of the puzzle, and make a smaller puzzle. I then repeat this reduction a few times. Instead of a 19x19 puzzle, by time I cut it down to 5x5 I could see what was going on.

Goto next topic

You must register and log in to be able to participate in this discussion.