Programming Puzzle: How to paint a board?

algorithm, language-agnostic, puzzle

Solution

This looks like a fun problem. Let me take a shot at it with some pseudocode.

Function MinPaints(Matrix) Returns Integer
    If the matrix is empty return 0
    Find all rows and columns which have a single color
    If there are none, return infinity, since there is no solution
    Set the current minimum to infinity
    For each row or column with single color:
        Remove the row/column from the matrix
        Call MinPaints with the new matrix
        If the result is less than the current minimum, set the current minimum to the result
    End loop
    Return the current minimum + 1
End Function

I think that will solve your problem, but I didn't try any optimization or anything. This may not be fast enough though, I don't know. I doubt this problem is solvable in sub-exponential time.

Here is how this algorithm would solve the example:

BBB
BRR
BGG
|
+---BRR
|   BGG
|   |
|   +---RR
|   |   GG
|   |   |
|   |   +---GG
|   |   |   |
|   |   |   +---[]
|   |   |   |   |
|   |   |   |   Solvable in 0
|   |   |   |
|   |   |   Solvable in 1
|   |   |
|   |   +---RR
|   |   |   |
|   |   |   +---[]
|   |   |   |   |
|   |   |   |   Solvable in 0
|   |   |   |
|   |   |   Solvable in 1
|   |   |
|   |   Solvable in 2
|   |
|   Solvable in 3
|                       BB
+---Another branch with RR ...
|                       GG
Solvable in 4

Problem

There is a `N x M` board we should paint. We can paint either an entire row or an entire column at once. Given an `N x M` matrix of colours of all board cells find the minimal number of painting operations to paint the board. For example: we should paint a 3 x 3 board as follows (R - red, B - blue, G - green): B, B, B B, R, R B, G, G The minimal number of painting operations is 4: - Paint row 0 with Blue - Paint row 1 with Red - Paint row 2 with Green - Paint column 0 with Blue How would you solve it ?

Original source