Is there a brute-force solution of this puzzle?

Question

There is a puzzle

Suppose a standard $8x8$ chessboard has two (arbitrary) squares removed. The only thing known is that these two squares have different colours. Is it always possible to place 31 dominoes of size 2x1 so as to cover all of these squares?

The answer is

yes

and there is very clever and fast prove:

Consider a closed curve, which covers all cells on the chessboard. You can cover chess board by dominoes simply putting them along the curve.
If two cells with different colours are missing the curve breaks to two curves, each has even number of cells, therefore they always can be covered with dominos.

I would like to know is there a realistic brute-force solution.

There is of course a brute-force solution, which considers all 32*32 combinations and solves them. But of course a man can't do it. Therefore, please understand, what I asking: is there a brute-force solution, which reduces all possible cells placements to several (let's say up to 10) options and simply check them one by one? If yes - please, show me it. If no - please prove it.

If there is such an solution - how can one modify this puzzle to rid of it (that means to increase number of options one needs to consider to be bigger than 10)?

Answer 1

In fact, if you try it a few times for specific cases, you find it is easy. There are lots of solutions. This is not a proof, but will convince most novices that it can be done.

Here is another way: Number the board $(0,0)$ through $(7,7)$ and let the removed cells be $(a,b)$, $(c,d)$ with $a \le b$ and $c \le d$ (rotate and mirror image if necessary to get this). As the colors are different, one of $c-a$ or $d-b$ is odd, the other even. If $c-a$ is odd, you can fill the rows above and below the holes with horizontal dominoes and the columns outside with vertical ones, leaving a rectangle $b-a$ times $d-b$ missing the corners. Fill the top and bottom rows with horizontals and the intervening rows with verticals.

Answer 2

The answer to whether this could be brute forced is yes. However, would it be feasible to brute force the answer? Probably not. Let's look at why:

A chessboard has 64 squares — 32 white, and 32 black. Removing one of each color gives us 32^2, or 1024 possible ways to arrange it. However, there are 4 lines of symmetry on the board. Each line of symmetry divides the final number of layouts by 2. $1024 / 2 = 512$; $512 / 2 = 256$; $256 / 2 = 128$; and $128 / 2 = 64$ possibilities. This can go one of two ways:

• Your friends don't realize this, so they start trying every possibility in the $32^2$ set. Depending on how they try to solve the domino layout, this could take a very long time. If they start noticing patterns, it will speed up, especially if they start noticing symmetry.
• Your friends already know all the symmetry, so they try the 64 board layouts. They'll only try as many as they need to. Even then, solution time will vary based on how they decide to try laying out the dominoes.

In the end, it's able to be brute-forced. However, even when you know there are only 64 unique ways to set up the board, the real brute force effort will be in arranging the dominoes, and this will be the most time consuming. Because your puzzle asks whether all of them can be filled with 2x1 dominoes, every board layout will have to be tried until they either find one that can't be 100% filled no matter what, or until they've tried all of them and found the condition to be true for each of them.

I'll give a little tip. Whenever the solution of a puzzle depends on combinations/permutations matching a certain condition, it can be brute-forced (think of it in the sense of passwords). In most cases, it only takes one combination/permutation that does or doesn't fit the conditions to solve the problem (the only situation I can think of where this is not the case is if it's asking how many meet the condition). Finding that will be a pain (like brute-forcing a bike lock).