Domino puzzles

Interesting puzzles can be posted here
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Domino puzzles

Post by Ruud »

I have built a new program called DominoCue. It is a generator, helper and solver for domino placement puzzles. I'm still refining it, but it can already create interesting puzzles.

In a Domino puzzle, you do not need to place any numbers, because they are already in the grid. All you have to do is draw outlines to create domino tiles containing 2 adjacent numbers. No diagonal connections are allowed.

The rule for Domino puzzles is very simple:

Complete the grid by in such a way that it contains all domino tiles with values 0-0 though 9-9 (*).

Tiles cannot be duplicated.

Here is the first domino puzzle. It is relatively easy, but not a complete walkover:

Code: Select all

.-------------------------------------------.
| 1   4   1   9   4   9   0   1   0   0   8 |
|   +   +   +   +   +   +   +   +   +   +   |
| 3   3   5   0   5   5   2   9   6   7   5 |
|   +   +   +   +   +   +   +   +   +   +   |
| 3   4   6   3   4   8   9   2   6   8   6 |
|   +   +   +   +   +   +   +   +   +   +   |
| 0   1   8   2   4   2   9   8   9   1   1 |
|   +   +   +   +   +   +   +   +   +   +   |
| 9   0   2   3   6   7   3   7   5   6   7 |
|   +   +   +   +   +   +   +   +   +   +   |
| 6   2   2   5   6   1   1   0   7   5   8 |
|   +   +   +   +   +   +   +   +   +   +   |
| 7   7   9   1   2   0   4   5   1   5   6 |
|   +   +   +   +   +   +   +   +   +   +   |
| 3   9   8   9   3   8   3   4   3   7   8 |
|   +   +   +   +   +   +   +   +   +   +   |
| 4   5   1   2   2   4   7   0   6   7   4 |
|   +   +   +   +   +   +   +   +   +   +   |
| 2   6   3   5   9   8   8   7   0   0   4 |
'-------------------------------------------'
Link to solution

(*) depending on the size. Smaller puzzles are possible, e.g. 0-0 through 6-6.
“If the human brain were so simple that we could understand it, we would be so simple that we couldn't.” - Emerson M Pugh
enxio27
Master
Master
Posts: 165
Joined: Sat Mar 17, 2007 1:20 am

Post by enxio27 »

So, if I understand this correctly, it's a jigsaw sudoku with all of the numbers already in the grid, but we have to figure out the placement of the jigsaw lines? Is that right?
Para
Yokozuna
Yokozuna
Posts: 384
Joined: Wed Nov 08, 2006 7:42 pm
Location: The Netherlands

Post by Para »

It is not a sudoku. Basically this grid is made up of domino tiles(you must have played that game) except the borders between the domino tiles have been taken away. What you have to do is figure out where the borders of the domino tiles are(or how you can create this grid of numbers with a set of dominoes).

This particular grid is made up of a double 9 domino set and each tile appears once in the grid.

Tiles:

Code: Select all

0-0
0-1 1-1
0-2 1-2 2-2
0-3 1-3 2-3 3-3
0-4 1-4 2-4 3-4 4-4
0-5 1-5 2-5 3-5 4-5 5-5
0-6 1-6 2-6 3-6 4-6 5-6 6-6
0-7 1-7 2-7 3-7 4-7 5-7 6-7 7-7
0-8 1-8 2-8 3-8 4-8 5-8 6-8 7-8 8-8
0-9 1-9 2-9 3-9 4-9 5-9 6-9 7-9 8-9 9-9
greetings

Para
Marlie
Master
Master
Posts: 167
Joined: Sat Dec 31, 2005 1:27 pm
Location: Venray Netherlands

Post by Marlie »

I don't understand. :cry: Can someone explain this in Dutch?
enxio27
Master
Master
Posts: 165
Joined: Sat Mar 17, 2007 1:20 am

Post by enxio27 »

Marlie wrote:I don't understand. :cry: Can someone explain this in Dutch?
Well, not Dutch, but maybe I can explain this way:

Imagine a set of dominoes laid out in a large square. Then imagine that the borders of the dominoes are erased, so that it looks like one giant tile with numbers. Your job is to recreate the lines that define the borders of the dominoes.

Contrary to my earlier guess, this puzzle has NOTHING to do with sudoku.
nj3h
Gold Member
Gold Member
Posts: 111
Joined: Mon Jul 10, 2006 12:58 pm
Location: Virginia / USA

Post by nj3h »

Is there any real logic to solving these kind of puzzles or is it just guesswork as you work your way through them?
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

No guessing is required.

You progress through the puzzle by eliminating possibilities and finding placements, same as in Sudoku. The candidates are all pairs of adjacent cells (numbers in the grid). To eliminate a candidate, simply draw the border between them. To place a candidate, draw the border around it.

Remember: Every tile combination will only be used once in the grid. If you have placed a tile, you can eliminate the remaining candidates for that combination.

Some techniques:

Hidden Single

There is only one possibility for a certain tile combination, e.g. 2-3 only occurs once in the grid.

Naked single

A cell has a single open border left.

Locked cell

A cell can only be used in a single combination, even though it is not yet clear in which direction, e.g.:

Code: Select all

 . 6 .
 6 1 6
 . 6 .
The cell containing the 1 can only be used in a 1-6 combination. This combination is not allowed anywhere else in the grid.

Claimed cell

All possibilities for a combination use the same cell. You can eliminate the remaining candidates that include that cell by drawing the borders.

Locked pairs, triples, etc.

N cells can only be used in N combinations. Eliminate remaining candidates for this combination in the grid.

Claimed pairs, triples

all candidates for N combinations use the same N cells. Eliminate other combinations for these cells.

Exception: When the cells are adjacent, this technique does not work when one of the combinations covers both cells.

Passages (even-odd rule)

When a portion of the grid is almost isolated, the last tile closing the gap can only go in a position that leaves an even number of cells in the isolated part.

Uniqueness

Take the following corner position:

Code: Select all

 | 3 2
 | 1 3
 +----
If we would choose a tile in one of the 2-3 positions, the other tile would be 1-3, both tiles in a 2x2 square. If this would be possible, so would the alternative 2-3- and 1-3 positions and the puzzle would have at least 2 solutions. Since I make these puzzles with a unique solution, you can eliminate both 2-3 combinations.

There are several more advanced uniqueness techniques.

With these techniques you can easily solve the posted sample puzzle.

Ruud
“If the human brain were so simple that we could understand it, we would be so simple that we couldn't.” - Emerson M Pugh
Para
Yokozuna
Yokozuna
Posts: 384
Joined: Wed Nov 08, 2006 7:42 pm
Location: The Netherlands

Post by Para »

Ruud wrote: Uniqueness

Take the following corner position:

Code: Select all

 | 3 2
 | 1 3
 +----
If we would choose a tile in one of the 2-3 positions, the other tile would be 1-3, both tiles in a 2x2 square. If this would be possible, so would the alternative 2-3- and 1-3 positions and the puzzle would have at least 2 solutions. Since I make these puzzles with a unique solution, you can eliminate both 2-3 combinations.

There are several more advanced uniqueness techniques.

Code: Select all

 | 2 3
 | 3 1
 +----
There's also this easy variant of the uniqueness test, where you eliminate one 1-3 and one 2-3 possibility.

Para
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

Thanks para, for adding this variant.

Here is a situation that I encountered several times in a grid:

Code: Select all

 1 2 2 1
When these are the only two possibilities for 1-2, placing 2-2 would eliminate both of them. Therefore you can eliminate 2-2.

These do not have to be in a single line, of course.

Anyone who has a catchy name for this technique?


Here is a simple isolation technique:

two opposite corners of this 2x2 square have been isolated.

Code: Select all

 +   +---+
   n   n |
 +   +   +
 | n   n  
 +---+   +
As a result, it is no longer possible to connect any of these cells outside the square.

You can now fully isolate this square:

Code: Select all

 +---+---+
 | n   n |
 +   +   +
 | n   n |
 +---+---+
Ruud
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

Here is a second puzzle, which requires several of the techniques explained above. The images are previews from the new DominoCue program.

Image

Link to solution

Code: Select all

.-------------------------------------------.
| 2   4   9   9   7   1   4   0   2   6   6 |
|   +   +   +   +   +   +   +   +   +   +   |
| 3   1   5   0   8   1   2   5   3   7   8 |
|   +   +   +   +   +   +   +   +   +   +   |
| 6   7   7   1   3   3   5   6   7   2   9 |
|   +   +   +   +   +   +   +   +   +   +   |
| 5   9   3   4   8   0   8   0   7   8   5 |
|   +   +   +   +   +   +   +   +   +   +   |
| 8   2   5   9   3   4   3   3   2   6   6 |
|   +   +   +   +   +   +   +   +   +   +   |
| 8   7   1   7   4   4   6   8   1   6   0 |
|   +   +   +   +   +   +   +   +   +   +   |
| 1   2   9   6   9   4   2   2   1   8   9 |
|   +   +   +   +   +   +   +   +   +   +   |
| 9   0   4   4   8   4   7   0   6   2   3 |
|   +   +   +   +   +   +   +   +   +   +   |
| 1   3   5   5   1   2   7   5   5   4   0 |
|   +   +   +   +   +   +   +   +   +   +   |
| 1   0   5   7   0   0   9   3   9   6   8 |
'-------------------------------------------'
Enjoy,
Ruud
“If the human brain were so simple that we could understand it, we would be so simple that we couldn't.” - Emerson M Pugh
Para
Yokozuna
Yokozuna
Posts: 384
Joined: Wed Nov 08, 2006 7:42 pm
Location: The Netherlands

Post by Para »

Hi

Here's some more.

Doubles rule

Code: Select all

 | 3 1
 | 3 1
 +----
The top 1-3 is not possible because it would force a second 1-3 in the grid.
This comes in many shapes.

And we can combine this with the isolation rules.

Doubles-Isolation

Code: Select all

 +   +   +
   6   6  
 +   +   +
 | 7   7 |
 +   +   +
 | n   n |
 +   +   +
 | n   n |
 +---+---+
The dominos can't be vertical [67] because then they would both be [67]

Or like this.

Code: Select all

 +---+---+   +
 | n   6   7
 +   +   +   +
 | n   n |
 +   +   +
 | n   n |
 +   +   +   +
 | n   6   7 
 +---+---+   +
There can't be horizontal [67] as it forces the other end of the closed area to [67] as well.

There are a few more extreme variants of this technique available.

greetings

Para
Last edited by Para on Thu Nov 29, 2007 2:17 am, edited 1 time in total.
Para
Yokozuna
Yokozuna
Posts: 384
Joined: Wed Nov 08, 2006 7:42 pm
Location: The Netherlands

Post by Para »

Ruud wrote:Here is a simple isolation technique:
My favourite variant is the 3x3 square.

Code: Select all

 +   +   +---+
   n   n   n |
 +   +   +   +
   n   n   n   
 +   +   +   +
 | n   n   n |
 +---+   +---+ 
Which fills like this:

Code: Select all

 +   +---+---+
   n | n   n |
 +---+   +   +
 | n   n   n | 
 +   +   +   +
 | n   n   n |
 +---+---+---+

Locked-Isolation
This is also a handy technique where a closed area needs an outie and it is the same at both ends eliminating that domino from the rest of the grid

Like this.

Code: Select all

 +   +
   5
 +   +---+---+
 | 2   n   n |
 +   +   +   +
 | n   n   n | 
 +   +   +   +   +
 | n   n   2   5  
 +---+---+---+   +
greetings

Para
nj3h
Gold Member
Gold Member
Posts: 111
Joined: Mon Jul 10, 2006 12:58 pm
Location: Virginia / USA

Post by nj3h »

Thanks to all for the great list of solving techniques.

OK, to get me started, take Ruud's first puzzle from a few days ago. What is a good first step to get me started?

Thanks,
George
Para
Yokozuna
Yokozuna
Posts: 384
Joined: Wed Nov 08, 2006 7:42 pm
Location: The Netherlands

Post by Para »

The first thing i always do is check the double digit stones(like 0-0, 1-1 etc.) as these are the easiest to find. I'd try that in both puzzles.

greetings

Para
Ruud
Site Owner
Site Owner
Posts: 601
Joined: Fri Dec 30, 2005 10:21 pm

Post by Ruud »

Yesterday I encountered a 3x2 isolation pattern:

Code: Select all

 +---+   +---+ 
 | n   n   n | 
 +   +   +   + 
   n   n   n    
 +   +---+   + 

resolves to:

 +---+---+---+ 
 | n   n   n | 
 +   +   +   + 
 | n   n   n |
 +---+---+---+


Ruud

Edit: I've called this the sixpack isolation
Last edited by Ruud on Sat Dec 01, 2007 7:36 pm, edited 1 time in total.
Post Reply