[EventHorizon]

Suppose you have an N by M chessboard with black and white squares. You can choose a rectangle, and all colors within it will change to the other (white to black and vice-versa).

1. What is the minimum number of rectangles you would need to invert to make the whole chessboard a single color?

2. What is the minimum number of rectangles you would need to invert to make the whole chessboard a specified color (white or black)?

3. Under what conditions are the answers to (1) and (2) equal?

The conditions involve the values for M and N.

[Guest]

I believe it has to do with them being even... Maybe if they're both even then they're the same... Or if they add up to an even sum then 1 and 2 are the same... Just thinking out loud here

[EventHorizon]

I believe it has to do with them being even... Maybe if they're both even then they're the same... Or if they add up to an even sum then 1 and 2 are the same... Just thinking out loud here

definitely on the right track

[Guest]

Without actually doing any tests, here are my initial thoughts:

I will refer to a rectangle with odd M and N as an "odd" rectangle, a rectangle with even M and N as "even", and one with one side of each as "mixed". Inverting an even rectangle would make no progress toward your goal, because even though you flip two corners of the same color, you also flip the opposite color on both corresponding rows and columns. Inverting a mixed rectangle doesn't directly make progress, because it switches the same number of black and white squares, but it could still help because you are flipping two corners of the same color on one edge. And when you invert an odd rectangle, you end up plus one (inverting a single square being the simplest example of this), but if M and N are larger than 1, you are flipping four corners at the same time, which is probably important for finding a solution that involves nesting or layering rectangles. So ...

While the simplistic approach would be to say the answer for an initial odd rectangle is (M*N-1)/2 - 2, and for a mixed rectangle (M*N)/2 - 1, and for an even rectangle (M*N)/2, I'm pretty sure there's a more effective approach that could trim off a few unnecessary inversions.

Edited April 4, 2008 by Duh Puck

[bonanova]

Let W = # white squares; B = # black squares.

If MN is odd, W and B differ by 1.

Making the board the color of the smaller value would reasonably take at least one addition move,

so answer [1] is a smaller number than answer [2].

If MN is even, W=B; that creates enough symmetry for [1] and [2] to have the same answer.

OK so what's missing now is the minimum number of rectangles to reduce one of the values

[W or B] to zero. It's clear that Min[W,B] is one answer for [1] and max [W,B] is an answer for [2].

I will stay with those answers, because it occurs to me that any selected rectangle changes W-B

by two [if it contains odd number of squares] or zero [if it contains even number of squares].

e.g. a 3x3 rectangle changes 4 of one color and 5 of the other, a net change of 1 for each value.

Thus if W or B is to be reduced to zero, W or B moves [rectangles] are required.

Single squares can get that done.

Nothing seems to be more efficient than flipping a single square each time.

[Guest]

Let W = # white squares; B = # black squares.

If MN is odd, W and B differ by 1.

Making the board the color of the smaller value would reasonably take at least one addition move,

so answer [1] is a smaller number than answer [2].

If MN is even, W=B; that creates enough symmetry for [1] and [2] to have the same answer.

OK so what's missing now is the minimum number of rectangles to reduce one of the values

[W or B] to zero. It's clear that Min[W,B] is one answer for [1] and max [W,B] is an answer for [2].

I will stay with those answers, because it occurs to me that any selected rectangle changes W-B

by two [if it contains odd number of squares] or zero [if it contains even number of squares].

e.g. a 3x3 rectangle changes 4 of one color and 5 of the other, a net change of 1 for each value.

Thus if W or B is to be reduced to zero, W or B moves [rectangles] are required.

Single squares can get that done.

Nothing seems to be more efficient than flipping a single square each time.

Yeah, when you put it that way, it does seem obvious that corners and nesting and layering are all irrelevant. There's simply no way to get around the simple solution.

[Guest]

Well.... if you think about it, an entire row or column is considered a rectangle, yes?

So then if you take every other row and invert like that, then take every other column, wouldn't that result in the least number of rectangles needed to make the entire board one color?

With B for black and W for white...

Like...

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

Invert every other row... which is only twice in this example

WBWBWBWB

WBWBWBWB

WBWBWBWB

WBWBWBWB

WBWBWBWB

Then every other column for either white or black.

WWWWWWWW BBBBBBBB

WWWWWWWW BBBBBBBB

WWWWWWWW BBBBBBBB

WWWWWWWW BBBBBBBB

WWWWWWWW BBBBBBBB

1 and 2 are equal when M and N are even numbers.

Or that's what I'm thinking...

[Guest]

Since I can't edit posts...

So in the N*M rectangle, these would be equations for the minimum number of rectangles.

If N and M are even, then to make is a solid color you need to use (N+M)/2 rectangles.

If N and M are mixed, it takes (N+M-1)/2 for either color.

If N and M are both odd, it takes (N+M-2)/2 for the color with more squares, and (N+M)/2 for the color with less squares.

Oh, and now I see, M OR N are even numbers, then the amount of squares is the same.

[Guest]

Yeah, when you put it that way, it does seem obvious that corners and nesting and layering are all irrelevant. There's simply no way to get around the simple solution.

But it would be wrong! I just wrote a quick little test app in Excel to demonstrate. Feel free to give it a try.

SquareChangeTest.zip

It seems to me ...

1.

eM,eN: M/2 + N/2

eM,oN: M/2 + (N-1)/2

oM,oN: (M-1)/2 + (N-1)/2

2. Assuming there are either the same number of black and white, or more white:

eM,eN: M/2 + N/2

eM,oN: M/2 + (N-1)/2

oM,oN: (M-1)/2 + (N-1)/2 for white, (M+1)/2 + (N-1)/2 for black

3. Every combination except where N and M are both odd and you're converting to the color with fewer squares.

Edited April 4, 2008 by Duh Puck

[bonanova]

That's what you get when you type before you think.

That would be me that I'm referring to ...

to the first flip of squares.

Clearly I need some sleep ... to all adieu!

[Guest]

For some reason, the version I uploaded craps out. Here's a new improved one with bug fixes and a clearer interface ...

SquareChangeTest.zip

Edit: Please note that you will have to enable macros in Excel. I assure you the file is virus free.

Edited April 4, 2008 by Duh Puck

[EventHorizon]

Well.... if you think about it, an entire row or column is considered a rectangle, yes?

So then if you take every other row and invert like that, then take every other column, wouldn't that result in the least number of rectangles needed to make the entire board one color?

With B for black and W for white...

Like...

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

Invert every other row... which is only twice in this example

WBWBWBWB

WBWBWBWB

WBWBWBWB

WBWBWBWB

WBWBWBWB

Then every other column for either white or black.

WWWWWWWW BBBBBBBB

WWWWWWWW BBBBBBBB

WWWWWWWW BBBBBBBB

WWWWWWWW BBBBBBBB

WWWWWWWW BBBBBBBB

1 and 2 are equal when M and N are even numbers.

Or that's what I'm thinking...

That is the right approach....I'll check the numbers from your next post a little later.

[EventHorizon]

Since I can't edit posts...

So in the N*M rectangle, these would be equations for the minimum number of rectangles.

If N and M are even, then to make is a solid color you need to use (N+M)/2 rectangles.

If N and M are mixed, it takes (N+M-1)/2 for either color.

If N and M are both odd, it takes (N+M-2)/2 for the color with more squares, and (N+M)/2 for the color with less squares.

Oh, and now I see, M OR N are even numbers, then the amount of squares is the same.

yep, looks like you got it.

Duh puck got it too.

GJ to both.