Dominoes and Chessboards
(c) 2005 by Jkb and JkbWorld
Reprinted from 01/20/2005
Introduction:
I was reading my Essentials of Artificial Intelligence book by Ginsberg and he mentioned a problem about placing 32 dominoes neatly on a chessboard. Then, after the dominoes were placed, two opposite corner spaces were cut off the chessboard and one of the dominoes was removed. The question was now, “Can you place 31 dominoes on an 8×8 chessboard with the corners cut off?”. He didn’t answer the question, leaving it as a task for the curious.
I knew I could simply look up the answer, but I wanted to write a program that could answer it for me. I also found a new Java library called POI that allows you to write to Excel files, so I wanted to use that at some point, too.
Theorizing:
The next day, I mentioned this problem to my mathematician friend, Charlie. We had been debating problems that could be solved by exhausting possibilities using the computer versus solving using a mathematical formula, so when we found this problem, we decided to discuss it some more over lunch. We went up to Burger King, and talked about it. We both agreed that we should be able to reduce the problem down to a 4 x 4 chessboard, so we attempted to arrange pepper packets to simulate a 4 x 4, but were unable to find the correct arrangement to solve it. We did not have proof that an 8 x 8 or 16 x 16 could not be done, however, but we were leaning in that direction.
Testing:
I wrote a program that would create an N x N, 2-dimensional array to simulate chessboards of different sizes. Basically, you would pass it a move by providing the coordinates of two squares. The program would then toggle the “empty/occupied” flag based on those coordinates. The program then built the search space by analyzing each square and reviewing the squares both to the left and right and above and below checking for empties. If it found two adjacent squares, it would add that as a possible move to the search space. Now, I initially tested a 4 x 4 and it took an incredibly long time to run. I optimized the code by removing the checks for blank squares to the left and checks for blank squares above, since the square above and square to the left would have already checked the current square.
I accomplished the corner cutting by making a move of (0-0-(N-1)-(N-1)), which “occupied” the opposite corners. All subsequent moves avoided these two squares. I didn’t put any input checking into the system, since the available moves are all generated from the program anyway.
I noticed that in preliminary runs, more data would be stored than I could view on a screen, even by scrolling, so I decided to write the combinations the program had tried to an Excel file.
Dominoes.java – Code to simulate problem.
Results:
My 4 x 4 analysis ran for 2 minutes (without Excel), producing no solutions. The Excel output was a flop. Because the program had to keep the Excel file in memory and continually write to the file, the memory was eaten at an alarming rate resulting in a crash caused by too small a heap size. I suppose I could tweak the JRE to get a larger heap space, but it’s not really worth it.
I ran one simulation (it may have been a 4 x 4 with no top-left optimizations, or an 8 x 8 with optimization) that ran for 30 hours on a Pentium 4 computer (also without Excel output) but did not produce a solution either.
I ran a 16 x 16 simulation on my office computer for a day and a half before killing the process because I knew it would not find a solution. I may run the program again another day just to see how long it takes to analyze the entire search space for the problem.
We arrived at the answer by looking at the relationship between a single domino and a chess board. When a domino is laying on a chess board, it covers up both a black and a white square. Opposite corners of a chess board are the same color, so if you cut off the black corners, you would have 30 black squares and 32 white squares. As you can see, there is no way to accomplish the task, so there was no point in continuing.
Conclusion:
This was just a fun little experiment with some Java Code. No earth-shattering problems or revelations. In the end, it turned out that a little bit of logical analysis can solve this particular problem better than trying all of the different domino combinations on a chessboard.
Sources:
Matthew Ginsberg, Essentials of Artificial Intelligence
Google Search for “Dominoes on a Chessboard” – I don’t remember the exact search I did, but I found a great page that had the solution.
Two quick notes:
1. The original version of this post had a light gray background, not white, the pictures of the dominoes along the right margin have a ghostly-white chessboard hiding underneath. The current white wordpress background does not do my freelance graphics skills any justice.
2. The Excel piece of this program was not very great to put up, partially because when you get larger data sets, the more lines got into the file, and when you exceed 65K lines or so in the old Microsoft Excel, you can’t open it. With the larger chessboard variations, you easily ran into this Excel limitation. The newest Excel should probably be fine. However, compiling and testing this will be left as an exercise to the reader. (I always wanted to say that!)