Sudoku is a simple game that was invented more than a century ago, but only started to get famous about 20 years ago, and suddenly it started appearing in the game sections of many papers, you could buy booklets full of Sudokus, there are Sudoku websites, applications and many more.
If you ever played Sudoku, you know that it can sometimes be very hard to solve, and it can become even harder when we start to use other variants of the game, like larger Sudoku with blocks. While it can be hard and time consuming to solve, in general the sudoku games that you see in the game sections are not impossible to solve. More over, once you solve a Sudoku puzzle, it is very easy to prove to other people that you know the solution – just show them the solution and they can check its validity quickly. However, what happens if you are given a Sudoku puzzle that can’t be solved? How can you even check that it can’t be solved, and if you know that it is unsolvable, can you easily prove it to other people?
The goal of this series of posts (next one is here) is to consider games like Sudoku (though a bit simpler), and try to learn how to find and use tools to show that in some cases they are unsolvable.
Playing with dominos
We start with a very simple game. We are given an board, and we are asked to cover it with domino pieces of sizes or . There are many ways to do it, but probably the easiest way is by filling each row with 4 domino pieces one after the other.
We can now consider this game for other board sizes. Clearly, if we take a board with 9 rows and 8 columns, the same method still works and we can cover it by dominos. If it has 8 rows and 9 columns, then each row has length 9, so we can’t cover it with pieces – it must have even number of cells to be covered by dominos of size 2. Luckily for us, we can instead cover each column, which has length 8, so we can cover the whole board.
But what happens if we have a board? We can’t cover each row separately or each column separately, but maybe there is still a way to cover the whole board (like in the example above on the right)? Well, exactly like in the 9 row example above we can use the same trick to show that we cannot cover it. No matter how you decide to cover the board, since each domino piece covers exactly two cells, the total amount of cells covered is going to be even. However, a board has a total of cells which is odd, and therefore cannot be covered by dominos. With this in mind we can immediately write the following result:
Claim: An board can be covered by a and domino pieces if and only if at least one of or is even, or equivalently the size of the board is even.
Lets try to understand what we did here. Given a board, there are possibly many ways to cover it, which can be really complicated. More over, if we look on “subcovers”, namely any covering of a subset of the board, there are even more options. While describing the covering can be complicated, since it might require a lot of information (for example, try to describe the covering in the example above on the right in words), just saying how many cells are covered is much easier – it is simply a non negative integer. This integer is not enough information to reconstruct the covering, but it already gives us some useful information. In particular, since it is so simple, it is easier to work with, and in this example it is easy to see that this number must be even, and therefore any board (not just rectangular) with odd number of cells cannot be covered with these dominos.
When parity is not enough
Can we reverse the claim above? Namely, if we know that the board has even number of cells, can we tile it using dominos? We know that for rectangular boards it is true, but what about general boards, for example like these ones with 14 cells each:
The example on the left can be covered by dominos. The first row needs only one domino, while the rest of the rows can be covered by two dominos each. However, no matter how hard you try, you will not be able to cover the second board. The question is, once you convince yourself this is true, can you find an easy way to convince other people?
Before, we used the fact that the size of each domino piece is cells and concluded that they can only cover an even amount of cells. However, these cells are not arbitrary two cells – they must be one next to the other. We can use this fact by coloring our board like a checkers board:
Now, every domino must cover exactly one white cell and one black cell, so any tiling with dominos cover the same amount of black and white cells. However, there are two more black cells than white cells, so we cannot cover this board.
Putting it more formally, lets denote for a given board it size by , and the number of white and black cells by . Then, we have proved that:
Theorem: Let be a board (with a checkerboard coloring). If can be covered by dominos , then (1) is even, and (2) . Alternatively, if either (1) or (2) don’t hold, then cannot be cover.
With this notation, we see that condition (2) implies (1), since
but as we saw above, condition (1) doesn’t imply (2). So while counting the white and black cells separately is a bit harder than just counting the total number of cells, it is still not that hard to do, and it gives us a lot more information that we can use.
The next natural question should be if is enough to show that the board can be covered. Here also this is not true. For example, a board with two cells, one white and one black, but not next to each other. But even if we ignore this non connected boards, it is still not enough, which can be seen in this example:
At this point, we can continue on and think of new properties like the two mentioned above that are (1) easy to work with, and (2) give more information about the board and whether it could be covered or not. There are certainly many more of these, and I will leave it as an exercise to find some interesting such properties.
From coloring to labeling
Let’s consider another point of view for these two conditions. In the checkerboard coloring, instead of counting black and white cells, we can give each cell a label corresponding to the coloring, and note that the total sum of cells under each domino is zero:
Now, the property that is exactly the same as saying that the total sum of the cells is zero. We could have done the same with the first property by giving all the cells the number and saying that the sum covered is even. This “number theoretic” approach can be very helpful, since it allows us to use everything that we know about the integers and summation. In particular, if instead of thinking about the standard integers, we think about the integer modulo 2, then these two labelings are the same (since ) and the two conditions are the same (an integer is even if and only if it is zero modulo 2). We will see this sort of application in the next post in this series as well.
One last bit of mathematical philosophy
Basically, what we did in the previous sections is to take elements from the world of domino covering, which can be really hard to describe, and map each one of them to a simple integer (the size) or a pair of integers (white\black cells), which also, fortunately, can be described using sums over integers. Both of these have much less information on the one hand, but are much easier to work with. This tradeoff between the information and simplicity is something that we see in many problems (and not only in mathematics). We call these invariants of the game, since they don’t change as we add more domino pieces (the parity of the sum in the first case, and the total sum in the labeling, or just the zero sum mod 2).
In our examples, both of the invariants are easy to describe, but moreover they are easy to compute. If this was not the case, than they would not be so helpful to us. But, there is actually one more thing both of these cases enjoy – they can be computed locally. By locally I mean that if we take a huge board, and we can only see a tiny portion of it, and someone does some changes only in this tiny portion, then we can say how it affects these invariant. Simply add or subtract the changes to the total sum. Not every property is like this – for example the property of the board being a rectangle. If someone adds a “corner” without seeing the whole board, we will not know if it becomes rectangular or not. This locality is very helpful, since it means that we only need to do a lot of small computations, instead of one big computation.
There are of course other invariants, and I encourage you to look for them and find this balance point between how much information you can retrieve from these invariants vs how hard they are to compute and work with. This domino game is a very simple game, and in the next post we will look at a more complicated game – the Peg Solitaire – and see how we can use similar invariants to show how show that it is not always solvable.