Domino Gridlock

Question

We have a 5x5 grid:

We also have some dominoes, 1 of each type with numbers 1 to 6 on each side. So we have the dominoes

1 | 1
1 | 22 | 2
1 | 32 | 33 | 3
1 | 42 | 43 | 44 | 4
1 | 52 | 53 | 54 | 55 | 5
1 | 62 | 63 | 64 | 65 | 66 | 6

How many ways are there to place the dominoes so

A: There are 7 spaces left uncovered and
B: No domino touches a number adjacent to it in the number line, or touches its own number?

Clarifications:

• Not all dominoes have to be used
• The dominoes must be in the grid
• There seems some confusion about the 'touching dominoes' part. I'll make it clearer:

1 | 35 | 4 Fine

1 | 33 | 1 Not Fine

And another example:

2 | 31 | 3 Fine

1 | 34 | 3 Not fine

And if they're on top of each other:

2 | 3
4 | 1 Fine

3 | 2
4 | 1 Not Fine

I hope this makes sense. I would also advice using a computer here

Answer 1

How many ways are there to place the dominoes?

Too many.

It is close to, and likely over, 1.232 * 10^16, or 12.3 Quadrillion for 9 dominoes.

I thought we should get an approximate bound on the size of this question. I set up a program to run a few calculations.

First I am going to cover physical locations of the dominoes, not their faces.

We are leaving 7 spaces uncovered, so we are only placing 9 dominoes on the board.

But, how many ways can we place the dominoes on a 5x5 board? For the first domino the are 40 pairs of tiles it could cover (20 horizontal and 20 vertical).

I had hoped to do this mathematically, unfortunately the options for the subsequent dominoes varies by the position of the first. If the first is placed in the corner of the board, the second has 36 possibilities. If it placed adjacent and parallel to a board edge, 35. Adjacent and perpendicular gives 34, and not adjacent to any edge gives 33. So I got a program to run some calculations.

The first number is how many dominoes you are placing, the second is the total number of ways to place the dominoes:

     1 40
     2 1,372
     3 39,792
     4 959,496
     5 18,840,000
     6 293,486,400
     7 3,507,073,920
     8 30,731,097,600
     9 185,341,685,760

To help establish a bound we are going to look at the number of ways the faces could appear in a sample domino layout. This should give an approximation but will not give an exact answer as some layouts will likely have a different number of possibilities.

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

Here the numbers are used to identify the distinct dominoes. How many ways can dominoes in these positions appear? The first domino has 36 options (6 options where the domino is a double, 15 options where it has the smaller number on the left, and 15 options where it has the smaller number on the right).

A second program was set to run with the specific restrictions of this puzzle.

      1 36
      2 1,040
      3 37,440
      4 258,880
      5 2,210,388
      6 21,445,228
      7 242,916,980
      8 2,235,646,272
      9 24,113,835,232

An astute reader may have noticed that both my calculations included some overlap. The both are allowing for all the permutations. Dividing my first results by nPn (to prevent counting of permutations in both results) gives:

     1  40
     2  686
     3  6632
     4  39979
     5  157000
     6  407620
     7  695848
     8  762180
     9  510752

And now multiplying the previous two results together gives:

     1  1,440
     2  713,440
     3  248,302,080
     4  1.035 * 10^10
     5  3.470 * 10^11
     6  8.742 * 10^12
     7  1.690 * 10^14
     8  1.704 * 10^15
     9  1.232 * 10^16

But this is all based on the representive domino layout shown previously. Using this alternative layout, where the dominoes are separated into two 'islands':

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

Gives 6.24 * 10^10 ways of having the dominoes, and gives a larger final value of 3.19 * 10^16. If someone can establish, definitively, the most and least complex domino layouts, these could be used to establish a proper bound on the number of possibilities.