How many ways can you divide a chessboard?

Post Reply New Topic

I've got a really good book of maths puzzles by a guy called H.E. Dudeney. There's one that's stuck in my mind for months. I still haven't looked at the answer because I'd rather work it out for myself. In fact, I might well avoid this thread if anyone replies!

The problem given in the book is this: how many ways are there to divide a 6x6 "chessboard" into two pieces of the same size and shape?

With a 4x4 "chessboard" there are six ways (with reversals and reflections not counted as different). See below.



What I'm really interested in is if there's a general formula for a nxn "chessboard". I'm worried that the back pages of the book might give this away! Either I'm being useless or this is quite a complicated problem.

It reminds me vaguely of partition theory, which is too complicated for me, especially since it's ages since I did any maths.

Print out a bunch of 6x6 grids and shade them. I did that and it took all of 5 minutes.

Hmm... I do remember a similar problem in the later chapters of my combinatorics book.

I haven't thought about this in depth yet... this is just going to be random babbling to try to get a sense of the problem.

If you counted all the ways of spliting a board in half... you would be choosing 8 out of 16... so that's a combination.

But since the two pieces have to be the same... whenever you choose one piece you have allready made your choice for the other piece...

Hmm... so breaking this down into choices at each stage of the problem.

Your first choice is free... so you have nxn...
The next choice is 2 less... since you can't choose the same piece or the coorisponding "opposite"... so you have nxn-2

Continuing forever untill you have no more choices to pick.

(nxn)(nxn-2)(nxn-4)(nxn-6)...(2)(1)

Of course this is counting reversals and reflections... so there'll have to be an additonal factor to count for that.

And of course this isn't counting that a "piece" has to be connected... which I think was implied from the begining.

Yeah this is a tricky problem... I need to break out some paper and pencil to dive right in.

Doesn't appear that bad though...

The easiest way is to start by looking at the simplest case (0x0), work upwards and then look for a pattern in the numbers. (All odd-sized boards have 0 as the solution, as one of the two pieces must always be larger.)

0x0: This could be 0 or infinity. (The trivial case will always fit into the pattern, since it can be no less valid than any other.)
2x2: Since we can't do diagonals, we're limited to 2.
4x4: 6, as described in original post.

The question is, what can you do with a 2 to make 2, a 4 to make 6 and 0 to make 0. Since 0 goes to 0, the equation probably doesn't add or subtract anything at the end. Now, if 2 goes to 2, you're multiplying and dividing by the same amount. 4 going to 6 gives some clues. 4 - 1 is 3 and 4 + 2 is 6. Something that is a fraction or multiple of 6 will make it easy to get the answer we want.

Let's examine the first possibility, subtracting by 1. 4 x (4 - 1) = 12. To make 6, we divide by two. Or maybe it's half of the board size (which, in the case of n=4 would be 2). Alternatively, we can just subtract 1 from the board size and then multiply by 2.

What about 2x2?

1) 2 x 1 = 2
2) 2 / 2 = 1. Wrong.

We can't just divide by 2, then. What about half board size?

1) 2 x 1 = 2
2) 2 / 2 = 1
From 1 and 2: 2 / 1 = 2. That looks ok.

How about just subtracting one and multiplying by 2?

1) 2 x (2 - 1) = 2. That works nicely as well.

Now, let's see what happens when we tidy these up.

1) n x (n - 1) / (n / 2)
2) Bringing the 2 to the top line, we get 2 x n x (n - 1) / n
3) Divide out the n's, and we get 2 x (n - 1)

So the two solutions are the same. We can therefore ignore the more complex one.

But does it work with our zero case?

2 x (0 - 1) = 2 x ( -1) = -2. Incorrect. This equation is invalid.

Now, let's try adding 3 instead.

Again, going back to our 4x4. (4 + 2) = 6. But the 2x2 board doesn't have four solutions, so the equation can't be that simple. We've got to put extra terms in, but the extra terms MUST cancel out completely for the 4x4 solution AND produce 0.5 for the 2x2 case. Well, n/4 would work. 4/4=1 and 2/4=0.5.

Let's just make sure.

4x4: 4 x (4 + 2) / 4 = 4 + 2 = 6
2x2: 2 x (2 + 2) / 4 = 2 x 4 / 4 = 2
0x0: 0 x (0 + 2) / 4 = 0 x 0 / 4 = 0

So we now have n x (n + 2) / 4, which produces valid results for all three cases. It's a quadratic solution, which makes sense as we're dealing with a square array.

Now, what is the solution for 6x6?

6 x ( 6 + 2 ) / 4 = 6 x 8 / 4 = 6 x 2 = 12

How about a standard 8x8 chessboard?

8 x ( 8 + 2 ) / 4 = 8 x 10 / 4 = 2 x 10 = 20

The largest of the Tafl boards (a European rival to chess that I happen to prefer) is 16x16.

16 x ( 16 + 2) / 4 = 16 x 18 / 4 = 4 x 18 = 72

Ob. Note: The division by 4 deals with the fact that you have 4-fold symmetry. If you were dealing with a different tessalating tile in a regular shape, you would want to use a different number.

That's not correct, a 2x2 board only has one possible way. All others would be a rotation or reflection. Also, simply following an apparent pattern doesn't prove a general problem.

What you should do is transform the problem into a simpler one. You'll notice that in all the examples the dividing line starts at the bottom on the left side and ends at the top on the right side, and that there is symmetry, ie if it starts one from the corner it ends one from the corner, starts in the middle ends in the middle. Additionally, it must pass through the exact center. So it's basically just finding paths from the starting positions which are all points on any one half of any one side of the board (left side of the bottom half, for example) to the center of the board. Keep in mind that you must be able to reflect the path also without it crossing itself. Also, if you start at the midpoint of a side, be careful of paths which are reflections of each other.

OK, I don't actually have a formula for this and I started doing it and there's a LOT of possible answers, but still I hope this helps

If you know that something is an nth order polynomial, you know you need (n+1) examples to find the function. This is always the case. One point defines a point. Two defines a line (no turning points). Three defines a parabola (one turning point), Four defines an upright S shape (two turning points) and so on.

Now, a chessboard is nice, in that almost nothing about a chessboard is going to increase linearly and there is not going to be a point of reflexion for the number of combinations. So you're dealing with a quadratic equation.

A quadratic equation with a single variable will take the form: y = a * x ^ 2 + b * x + c. All you need to do is find the correct values of a, b and c. Hence the need for three different values of x and the corresponding y. With those three values of (x, y) you can establish the values of a, b and c. There can be only one possible set of values, when using three distinct points to solve a quadratic.

Now, let's use the values you've got (ie: eliminating symmetry) and see if that still produces a unique solution.

x = 0, y = 0.

0 = a * 0 ^ 2 + b * 0 + c
c = 0

x = 1, y = 1

1 = a * 1 ^ 2 + b * 1 + 0
1 = a * 1 + b
1 = a + b
b = 1 - a

x = 2, y = 6

6 = a * 2 ^ 2 + b * 2 + 0
6 = a * 4 + b * 2
6 = a * 4 + (1 - a) * 2
6 = a * 4 + 2 - 2 * a
6 = 2 * a + 2
4 = 2 * a
2 = a

b = 1 - a
b = 1 - 2
b = -1

This creates a solution of: (solutions) = 2 * columns ^ 2 - columns

This, we can factor out to: (solutions) = (columns) * (2 * columns - 1)

Thus, this is the general solution to a two dimensional square board with an integer number of squares. It does not solve general rectilinear problems or problems in a greater number of dimensions.

Ok, so using this, what do we get for a 6x6 board?

(solutions) = 6 * (2 * 6 - 1) = 6 * (12 - 1) = 6 * 11 = 66

For an 8x8 board, we'd get:

(solutions) = 8 * (2 * 8 - 1) = 8 * (16 - 1) = 8 * 15 = 120

And the 16x16 board?

(solutions) = 16 * (2 * 16 - 1) = 16 * (32 - 1) = 16 * 31 = 496

Can you use patterns to solve problems in general? Sometimes. Proof by induction is a perfectly valid mathematical technique.

Can you use known examples to solve problems in general? So long as there are enough such solutions, then you can solve ANY linear series of polynomials of ANY order and of ANY number within the sequence, so long as there are no discontinuities in the region you are examining through the examples. For equalities, you need one solution per unknown. It even works if the solutions are inequalities, but you need rather more examples then.

If you are not dealing with polynomials or anything that you can turn into a polynomial by applying a transform, solutions can be a bit trickier. However, for these kinds of puzzles, nobody is going to tell you to find the second order differential of a chaotic function. And if they did, you'd skip the problem by answering (correctly) that there are no solutions.

The problem's super-exponential, not polynomial. There are a minimum (n-1)^(n/2) solutions. For example, take a chessboard of side 20. In each of the first 10 columns, you can paint the bottom 1-19 tiles red, and the remaining blue. This creates a pattern that is solid (one piece) and can be reflected. It also allows for 19^10 possibilities. Also, this doesn't count the many many more possibilities of patterns which interlock or go back and forth or have columns of a solid color. But for a chessboard of size 6, it gives a quick 125 possibilities

((n-1)^(n/2)+1)/2 rather, my mistake. Half of those are redundant. I just realized it didn't work with the chessboard of size 4, but this should be correct.

If n=0,

n-1 = -1.
n/2 = 0
-1^0 = 1
1+1 = 2
2/2 = 1

So, this would say that we can divide a chessboard of zero size once. A zero-sized board is a point. Whichever side you put the point on, the line MUST go on the other, so it can't be symmetric. The super-exponential solution breaks on an boundary condition.

If n=1,

n-1 = 0
n/2 = 0.5
0^0.5 = 0
0+1 = 1
1/2 = 0.5

This is a non-integer solution, so invalid, so saying you can't divide a 1x1 board. That's what I would expect.

If n=-2,

n-1 = -3
n/2 = -1
-3^-1 = -0.33
-0.33+1 = 0.67
0.67/2 = 0.33

This doesn't seem to make much sense. The laws of symmetry apply perfectly well for objects along the negative axis or even in the depths of complex numbers. Where there's a mix of real and imaginary solutions, you might need to take the modulus, but the equation shouldn't break. A square is a square is a square, no matter how real or imaginary.

What happens with a chess board of size 0 or a negative size or any size other than a positive even integer is irrelevant. You're trying to apply continuous graph theory to a discrete problem. But just to nitpick, there would actually be 1 way to divided up a chess board of size 0. That is, nothing on one side, nothing on the other.

That being said, I don't think you're getting this. It's basically like this: You can take your chess board of size 6, and divide it up so in each column some number on the bottom are in one group, and the rest are in the other. So here are possible answers:
1 1 1 5 5 5
1 1 2 4 5 5
1 1 3 3 5 5
1 1 4 2 5 5
1 1 5 1 5 5
1 2 1 5 4 5
1 2 2 4 4 5
1 2 3 3 4 5

Well, you get the idea. You can go up to 3 3 3 3 3 3, which is the halfway point. Any beyond that will be a reflection of one you already considered. Go ahead, draw these out and you'll see that they're all valid and unique, and do the combinatorial math and you'll see that the formula I gave is correct. Also, this is not a final answer, as there are other possibilities not covered in this formula, but it is a lower bound, and a um... I said superexponential before but that may not be the right term. Anyway, it's O(n^n), which is greater than exponential and certainly greater than polynomial.