Friday's Dominosa Problem

Question

Dominosa is a logic puzzle with a similar feel to Sudoku, and I've recently added it to Donimoes, my collection of domino puzzles and games. Given a grid of numbers, you have to lay out the dominoes so they match the numbers, without duplicated or missing dominoes. See Monday's problem for complete rules and and an example solution.

Today's problem is even bigger and more challenging than Wednesday's. Good luck, and post your solution as an answer.

I hope you enjoyed these puzzles, watch for something a little different tomorrow.

Answer 1

Here is the solution:

Explanation (red):

There's only one place for the 6-6.
In the bottom left corner, the 2 is always connected to a 4 so we can draw lines between the other 2-4 combinations in the grid. In particular, this forces the 2-3 in the bottom row, which means the bottom right corner is the 0-1.
The bottommost 2 in the right column can't be used as 2-3 anymore, so the only option there is a 2-2.
We can draw a few more lines between combinations that are already taken:

Continued (orange):

Now, if there would be a 5-0 in the second row from the bottom, that would lead to a 3-4 directly below it, and a 4-3 to the right (either horizontal or vertical). So the 0 there must be used together with a 4 (below or to the right of it).
That means the 0 in row three, column five must be used together with the 3 to its right.
Also the 2 in the top row needs to be used with one of the 0s.
The 0-5 needs to be in the leftmost column, but if it were on row three and four, it would also cause a 0-5 on the top two rows. So it needs to be in the top two rows, and the only place for the 0-0 is the third row.
About here I also realized there's only a single position for the 1-2 left:

Continued (yellow):

The 6 in row four, column 2 has only 5s as neighbours, so in the upper right corner, the 5 needs to be paired with the 3.
That means the 5 in row six, column 4 needs to be paired with the 2.
The only remaining place for the 2-6 is the rightmost column:

Finally (green):

The 5 in the second column from the right must be paired with a 1; therefore, the 5 in row four, column three must be paired with the 6 on its left.
From there, you can use geometry to fill all remaining pairs, you don't need to look at the numbers anymore.

Thanks for making these puzzles and enjoy your well-deserved weekend!

Answer 2

Wrap-up: The Making Of Dominosa Problems

This is not a solution to the puzzle, but provides notes from its poser. This type of answer has been approved by the community.

Caution: This post may contain spoilers.

---

Inspiration

As I mentioned in the introduction to Monday's problem, this is an old puzzle and the most common domino puzzle that I see online. It was invented by O.S. Adler in 1874.

I took a long time to add this puzzle to my collection, because I found it tedious to keep searching for unique numbers. After some research, though, I learned that people have found many other techniques for solving that aren't as tedious. After adding it to my collection with a set of problems, I decided to celebrate by posting three new problems here on Puzzling.SE.

Creative steps

A lot of the pieces were already in place when I started working on this puzzle. I had created several other domino puzzles and games, so I had a Python program to generate diagrams and generate other puzzles. For this puzzle, the diagrams are a little different, though. They show a grid of numbers, but not which ones are connected. After some experimentation, I came up with this:

I used double lines as a guide for the solver to fill in the domino borders as they figure them out. The lines are faded so they won't distract from whatever the solver writes.

I was pleased with the way the diagrams turned out, and I enjoyed using them to solve Dominosa problems that other people had created. Now, I just had to figure out how to create new problems for my collection.

Logistical steps

Considering how much was already in place for this puzzle, it took me a long time. I started seriously thinking about it six months ago, started writing the software about four months ago, gave up for about two months in the middle, and then really worked on it for the last month.

The first thing I did to explore the problem was to write a brute-force solver. It had a couple of basic solving techniques for unique numbers and dominoes forced by their neighbours, but when those ran out, it would guess at domino locations until it came to an impossible situation, then it would backtrack. It's very inefficient, but it let me generate a bunch of random layouts and report the ones with unique solutions.

That let me try solving a bunch of problems, but I was stumped on how to proceed. How would I analyse what makes a problem interesting so I could find the good ones? I put the challenge aside for a couple of months and worked on other things.

The first thing that felt like progress was to come up with a better algorithm for solving Dominosa problems. It was based on solving hints I found on other web sites, but I made it rigorous enough that I could write it up as a program.

Keep track of the following state while you solve a board:

• Each pair of cells is in one of these categories:

  • undecided - all pairs start in this state, and they might end up joined or not (space)

  • newly joined - they must be joined in the solution, but they haven't been checked for duplicates or neighbours (j)

  • joined - they must be joined in the solution, and they've been checked for duplicates and neighbours (|, -)

  • newly split - they must be split in the solution, but they haven't been checked for duplicates (s)

  • split - they must be split in the solution, and they have been checked for duplicates (S, ~)

To solve a board, follow these steps, updating the state of each pair as you go. Always start with rule 1, and check each rule until you find a match. As soon as you finish any rule, start again with rule 1.

1. Look for a cell that only has one neighbour, and join it with its neighbour in the newly joined state. Particularly check near the last pair you joined.

2. If you have a newly joined pair, put all of its undecided pairs with its neighbours in the newly split state. Based on the newly joined pair, check for the same pairs elsewhere on the board, and mark all of them as split. Move the newly joined pair to the joined state.

3. If you have a newly split pair, look for the same pair elsewhere on the board to see if there is only one undecided pair like them. If so, mark the unique pair as newly joined. Either way, mark the newly split pair as split.

4. If all of a space's undecided neighbours are the same, you know it will join one of them. Look for the same pair of undecided numbers elsewhere on the board, and mark them as newly split.

5. Look for unique pairs of undecided numbers, and mark them as newly joined. (This is the tedious part.)

6. If a pair of undecided numbers appears more than once on the board, but all of the pairs share one space, then you know that space must join to the other number. Mark any other undecided neighbours as newly split.

7. If none of the other rules apply, guess at a domino's placement by marking a pair as newly joined. If it later causes a contradiction, backtrack and mark it newly split. (This would be very frustrating when solving by hand, so try to avoid needing it.)

Once I had that, I could analyse a partially solved board, find the available deductions, and pick one to use. I fit that into the puzzle generation framework I used on other domino puzzles. It tracks each state of the solution as a node in a graph, and all the possible deduction steps as edges. Once it has explored the whole graph, it finds the shortest solution and then scores that based on features that I think will make problems interesting to solve.

Once I had a way to generate puzzles and score them based on how interesting they were, I used evolutionary search to make small changes (mutations) and then repeat with the most interesting ones (selection). To score them, I tried to find solutions that required lots of different deduction rules, but minimized the number of times you needed the tedious rule of searching for unique numbers.

Resources

I don't remember where I first learned about Dominosa, it might have been from Martin Gardner's Mathematical Games column in Scientific American.

The best source I found for solving hints was puzzle-dominosa.com.

I have a set of Python scripts for generating several different kinds of domino puzzles on GitHub.

For earlier puzzles, I used DEAP for evolutionary search, but I found it really frustrating to work with. This time, I followed a simpler tutorial and built my own search framework.

Takeaway

I was surprised that I ended up liking Dominosa much more than I expected. There's something about the process of grinding away making small deductions that suddenly release a chain of forced placements that I really like. I still try to minimize the number of tedious searches, though.