18
$\begingroup$

Imagine you have a $8 \times 8$ completely white field of squares on your screen. Now you can click on any square. When you do this, all the squares in that column and line (including the one you clicked on it) will change their color (if it's white it will be black and vice versa). How many steps at least would it take to create a standard chessboard?

I tried it manually but it got too complicated and I lost track of the situation. But if I could tell my problem to Mathematica it could be very easy. Is there a way to write code to calculate this? Or even a formula to do this manually without any program?

$\endgroup$
  • 2
    $\begingroup$ I don't understand why this question migrated from Mathematica's site. It seems to belong there. $\endgroup$ – DavidC Sep 5 '15 at 17:30
  • 1
    $\begingroup$ exactly I think this question is equally suited for mathematica and infact I wrote a code for this. $\endgroup$ – Hubble07 Sep 5 '15 at 17:35
  • 1
    $\begingroup$ I have a proof without advanced math, will post in detail tomorrow (past 2 AM here). In short: For each row/col, there must be an even number of clicks outside it (because it would end up with an odd number of black cells otherwise). For this, the total number of clicks must be even. This leads to the number of clicks being even in every single row/col. Take a row. There is no net change from clicks there (everything flipped even times). cont $\endgroup$ – MPeti Sep 6 '15 at 0:31
  • 1
    $\begingroup$ Look at the cells. If a cell was clicked, it has an odd number of clicks outside the row in its column, so it will be flipped in the end. Similarly, a cell not clicked will not be flipped. So we have to click every single cell whose color we want to change. This means there is no going lower than 32. $\endgroup$ – MPeti Sep 6 '15 at 0:35
  • 1
    $\begingroup$ @MPeti: Yes your solution is the same as the one I got. It's also more illuminating, so please post it! For getting total number of clicks to be even, a more direct way is to see that every move changes an odd number of cells so we need an even number of moves. $\endgroup$ – user21820 Sep 6 '15 at 9:02
3
$\begingroup$

Since you had asked this first at Mathematica site. I made a small program where you can play around to see the variations graphically.

Run the code in Mathematica and it will generate the dynamic grid shown below.

 chess = Table[0, {i, 1, 8}, {j, 1, 8}] 

 toggle[m_] := Which[m === 1, 0, m === 0, 1];

 click[m_, n_] := Module[{},
  Table[chess[[m, j]] = toggle[chess[[m, j]]], {j, 1, 8}];
   Table[chess[[j, n]] = toggle[chess[[j, n]]], {j, 1, 8}];
   chess[[m, n]] = toggle[chess[[m, n]]];
     ]     

  Row[{Column[{Button["Reset", chess = Table[0, {i, 1, 8}, {j, 1, 8}]], 
  Grid@Array[Button[{#1, #2}, click[#1, #2]] &, {8, 8}]}], 
   Dynamic[ArrayPlot[chess, Mesh -> True, ImageSize -> 300]]}]

You can click on the elements to see the change. enter image description here

$\endgroup$
  • $\begingroup$ Wow, that was very helpful. Very nice code! Thank you! Can you ask Mathematica now to try all the possibilities to find the matching answer and count the minimum amount of steps it needed to find the solution? Is that possible? That would be very nice. $\endgroup$ – Masirius Sep 5 '15 at 18:15
  • 2
    $\begingroup$ Brute forcing through all variations would be definitely beyond the memory capabilities of mathematica. I'm not even sure if the total no of variation are finite, I think it depends on how you define a variation. If 1 variation means 64 ordered clicks then there are 64! possibilities which is huge. Maybe there exists some neat symmetry arguments which can reduce the sample space. $\endgroup$ – Hubble07 Sep 5 '15 at 18:49
  • 2
    $\begingroup$ "Clicking" is commutative, so the order doesn't matter. This reduces the space to $2^{64}$ possibilities. The method I described in my answer also gives you every possible combination of clicks that lead to a chessboard [if any]. You just need to determine the kernel in the corresponding matrix. $\endgroup$ – Dominik Sep 5 '15 at 19:02
  • $\begingroup$ I tried it manually and found 32 steps. I began with the odd numbers in the first line and the even numbers in the second line. Than again the odd numbers in the third line and the even numbers in the fourth line and so on. This will take 32 (4x8) steps to create a chessboard. I'm not sure whether there is a faster way to get it. $\endgroup$ – Masirius Sep 5 '15 at 19:13
17
$\begingroup$

Hint: Try to convert your problem into solving a $64 \times 64$ system of linear equations over $\mathbb{F}_2$.

$\endgroup$
  • $\begingroup$ Thank you for your answer but I'm not a mathematician. So I didn't understand what you mean. Can you explain it or even demonstrate it? $\endgroup$ – Masirius Sep 5 '15 at 16:46
  • 1
    $\begingroup$ There is a MathWorld article about a similar problem, but 'm afraid you will need some knowledge in linear algebra to solve any of these two problems. $\endgroup$ – Dominik Sep 5 '15 at 16:54
  • $\begingroup$ Hi Dominik; I could use a little help with that also. Oh, just saw your new comment, thanks! $\endgroup$ – bobbym Sep 5 '15 at 17:01
  • 4
    $\begingroup$ This is good question, which on this site often means the answer requires some cleverness or thought. In this case, the cleverness requires some linear algebra. Unfortunately, it's hard to imagine a simpler answer than what @Dominik has here. That being said, reading about using matrices to solve systems is super useful knowledge anyway. $\endgroup$ – Zach Stone Sep 5 '15 at 17:06
  • $\begingroup$ Can you expand your answer now it's accepted? I'd like to understand this :-). $\endgroup$ – YoTengoUnLCD Sep 6 '15 at 5:56
14
$\begingroup$

A valid proof without advanced math:

No cell should be clicked more than once.
By clicking somewhere two times, you're just reversing your changes. Since the order of clicks does not make a difference, this holds even if you do other clicks between these. So we only need to consider one or zero clicks on each cell.

The number of clicks outside each row/column must be even.
If there was an odd number of clicks outside a given row, the number of cells changed in that row would be odd, leading to an odd number of black cells there. (Clicks in the row don't affect this, since they change all cells in that row).

The number of clicks in total must be even.
Each row changes 15 cells, so an odd number of clicks in total would lead to an odd number of color changes, resulting in an odd number of black cells on the whole board. (thanks user21820)

The number of clicks inside each row/column must be even.
Subtract the number of clicks outside a row (an even number) from the number of total clicks (another even number). The result will be even.

A cell will be changed in the end if and only if it was clicked.
Look at a row. The clicks in that row leave its cells unchanged, since there is an even number of them. Which cells are changed by the clicks in other rows? We can use the fact that there must be an even number of clicks in each column as well to tell.

Look at the cells in the row:

  1. If it was clicked, there is now one click in its column. There has to be an odd number more in other rows. These are the clicks outside the row that change this cell. Since there is an odd number of them, the cell will be changed in the end.
  2. If it was not clicked, there has to be an even number of clicks elsewhere in the column. This means the clicks outside the row also leave the cell unchanged.

The optimal solution is 32 clicks.
We proved that we need to click all the cells we want to change to get a chessboard coloring. There are 32 of these, so that's the best we can do. In fact, that's the only number of moves which can lead to a chessboard coloring if we don't click any cell twice.

$\endgroup$
  • $\begingroup$ This seems correct, bravo! Moreover, it shows that the result is always the same for every even size of board (the used facts are that the total number of black squares then is even, and that the number in each row and column is even, so that the purported method actually does provide a solution). For odd numbers the situation is different, for instance there are no solutions at all for sizes $3$ or $5$, if the corners are black. $\endgroup$ – Marc van Leeuwen Sep 6 '15 at 14:06
  • $\begingroup$ Nicely done - much more elegant and concise than I was working towards. $\endgroup$ – Pieter Geerkens Sep 6 '15 at 14:11
  • $\begingroup$ @MarcvanLeeuwen "no solutions for 3 or 5 if the corners are black" - would you elaborate? It seems to me that if the "all white except corners" situation is unsolvable, then so is the "all white" - if you click all corners, only they will change. So I don't see why you specified that position. Or if you meant that we want to reach the "chessboard with black corners" position: if you click every single cell, all colors will flip, so the two chessboard positions are also reachable from each other. $\endgroup$ – MPeti Sep 6 '15 at 15:18
  • $\begingroup$ @MPeti: All I meant is there are two different kinds of odd size square checker boards, distinguished by the common colour of all four corners, and I did only claim impossibility for the one with black corners. But I now realise that the argument you gave shows that the other kind must then also be unsolvable. $\endgroup$ – Marc van Leeuwen Sep 6 '15 at 15:35
4
$\begingroup$

Note that on the starting board, assumed all white without lack of generality, there are 32 squares coloured correctly. One then can trivially verify that after a single click on any square of this starting board there are 33, or 32 + 1, squares coloured correctly.

Let's analyze that first move more closely. It accomplishes the reversal of precisely 15 squares: the square clicked; the other seven on its row; and the other seven on its column.

To arrive at a chessboard from an originally all-white board the final white squares must have been swapped an even number of times, and the black squares must have been swapped an odd number of times. It is trivial to verify that by clicking once on every black square, in any order, a chessboard will result. We need to prove that this is minimal.

This 32-move solution performed 32 * (7+7+1) = 32 * 15 = 480 colour swaps of a square. Note further that a single click can only possibly reach 7 black squares (clicking a black square) or 8 black squares (clicking on a white square). Thus to cover all black squares requires a minimum of 8 clicks (A click is required on each of the 8 rows, as well as on each of the 8 columns.)

Any set of 8 clicks will perform 8 * 15 = 120 colour swaps. Any selection of 8 clicks that covers all black squares will have swapped all squares on the board twice, except the 8 squares clicked which will have been swapped once only. Of course 64 + 64 - 8 = 120 as noted above. Therefore only 8 squares (net) will have changed colour.

Four other such patterns can at most also swap a net of 8 squares each.

By composing four such suitable patterns we can finally cover a net of 32 colour swaps, but this is our already discovered possible solution; so it is both possible and minimal. This relies on the commutativity of clicking, which is trivially proven.

This proof does not have all the rigour I would like, but should suffice to guide someone to a rigourous proof.

$\endgroup$
  • 2
    $\begingroup$ +1 for at least attempting to prove minimality. However the proof is not only less than rigorous, I don't think it actually leads to a proof in any obvious way. First off, the claim to need at least 8 clicks to cover all black squares is wrong: choosing any 7 squares on the white diagonal also does this. But more fundamentally, you need to reason about all subsets of less than 32 squares, showing that none will work. They need not allow a partition into subsets of 8 that you are using. In other words, you could only show that one limited strategy won't find a better solution. $\endgroup$ – Marc van Leeuwen Sep 6 '15 at 9:39
  • $\begingroup$ @MarcvanLeeuwen: I'm working on that; . It's been a long, long time since I did any rigorous mathematics My notes below (deleted 2nd solution) shows that an even number of clicks is required.. Hadn't thought of the 7 white squares, but as white squares need to be swapped an even number of times the only click to pair it up with for a net contribution is to unclick the same square again. $\endgroup$ – Pieter Geerkens Sep 6 '15 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.