The minimum number to make the whole chessboard black

52 Views Asked by At

A 7x7 chessboard that painted in black-white (the corners are black). The operator "inverse - change color" can be run on a single row or column in the panel. the goal is to make the whole panel black.

Ques: what is the minimum number of operations to achieve the goal?

Note: i'm forcing to use a Metric/Index; that relates to the area of specific squares in my answer

1

There are 1 best solutions below

5
On

The optimal number of operations is $6$. This is when each of the columns/rows which have white squares at their edge are converted in turn. i.e. change the colour of every row which has a white square at the edge of the board. Then do the same for every column.

To prove that this is optimal, consider the final move in this process. In order for every square to become black after an operation is performed, the entire row must be white. If we then select a row and say that this row will be the final row to be converted, we must first convert every column which has a black square in the selected row. After doing this we can convert the remaining white rows until we get to the originally selected row. Note that there are two cases when choosing the 'final row' - either it has $3$ or $4$ black tiles originally. In order for the optimal operation to be performed we need to select a row with $3$ black tiles so that only $3$ corresponding columns need to be converted.