Dominos

Stu's Puzzle

Stu posted this puzzle the other day. The challenge is to arrange the dominoes so both vertical columns and both horizontal columns add up to the same number. Now you could go get some dominoes and see if you could accomplish this, but I thought it was a good opportunity to see if I could write a program to solve it. There's only eight dominoes, so the number of possibilities is an easily managed number. That would be 8! (factorial) which is 40,320. However each tile can be placed in either to two ways, so we need to multiply our possible combinations by 2 to the 8th power, which is 64, which gives us a tad over 2.5 million. That's still easily within reach of even a small, weak computer.

If we look a little closer, we realize we don't need to test every possible arrangement. We only need to place our first tile in one of the two positions in the top row. Any solution with the first tile in one of the other sides can be rotated to have the first tile in the top row.

With the first tile is in the first position, the number of possible arrangements is 7! Likewise, if the first tile is in the second position, there are another 7! possibilities. So we have 2 times 7!, so we have reduced the total by a factor of 4.

Also note that only the pieces in the corners are going to effected by their orientation. The other pieces may be placed either way without affecting the sums. So that reduces the total possibilities by a factor of 16 (2 to the 4th power).

There is one tile that has the same number of pips on both sides (4 x 4), so it's orientation isn't going to matter either. That will only affect the total if it is placed in a corner, which will only happen half of the time, that will reduce the 16 possibilities by 4, so now we have 2 x 7! x 12 which is a little over 120,000.

Okay, now we know the size of the problem, all we need is the code to try all 120,960 of these possibilities and find one that meets Stu's criteria.

The first part, creating all possible arrangements of tiles is easy. Simply generate all the permutations of 7 digits and use that list to place the tiles on the board. Selecting the orientation of the four corner files is easy as well. Simple count from 0 to 15 and use the binary value of the counter as a bit mask to determine if a tile should be flipped or not.

The last part is skipping the 4 by 4 tile. We do this by creating a mask that indicates which of the four corners, if any, holds a double tile. As we iterate through the bit mask, we AND these two masks together, any non-zero value indicates at least one or the corners holds double that is to be swapped (end for end), so this combination does not need to be tried as it will have the same results as the one where the double tile is not swapped.

We need to generate all possible permutations of a list of 8 numbers. One way to do this is to use a recursive procedure. You call it once for the first number, and then it calls itself for the second number, and it keeps doing this until it has placed the last number and then it calculates the various sums based on the order represented by this list of eight numbers.

There are two ways to do this. One is that each level is assigned a spot in the list and iterates through the numbers one through eight. The other is that each level is assigned a number and it iterates through the eight possible positions. Either one will work, you just need to decide which one to use.

However, we don't really want ALL possible permutations, we only want those that have the first tile in either the first or second position. The first position is easily handled, simple set it and let recursion sort out the remaining seven. The second position is the one that is giving me trouble, mostly because I was short of sleep last week.

We need to use the second method: each level is assigned a number and it iterates through the eight possible positions, except we are really using zero through seven, and we aren't using zero because we have already placed it.

The first method gave me trouble because when you put the first (zero-th) tile in the second spot to begin with, when you get to the second level you have already filled it so you get confused and end up making a hash that doesn't work. Use the second method. Once I got some sleep it was obvious.

I finally finished the program. You can find it on github along with a text file showing all 164 solutions.

Here is the last solution the program found:

counter: 120233 skipped: 39592 solved: 164 permute: 40376521 Sum: 20
╔═══╦═══╤═══╦═══╤═══╗
║ 3 ║ 4 │ 5 ║ 4 │ 4 ║
╟───╬═══╧═══╩═══╬═══╣
║ 6 ║           ║ 6 ║
╠═══╣           ╟───╢
║ 6 ║           ║ 2 ║
╟───╢           ╠═══╣
║ 4 ║           ║ 5 ║
╠═══╬═══╦═══╤═══╬───╢
║ 1 │ 5 ║ 6 │ 5 ║ 3 ║
╚═══╧═══╩═══╧═══╩═══╝
Total solutions found: 164
Total failures: 120796
Total permutations tried: 120960

P.S. Experimenting with formatting the solution diagram.