Minimum number of clicks to solve Flood-It-like pu

Question

I have grid N × M in which each cell is coloured with one colour.

When the player clicks on any cell of the grid of colour α, the cell in the top-leftmost corner of the grid, of colour β, receives the colour α, but not only it: all those cells which are connected to the source by paths which use only the colours α or β also receive the colour α.

The connection between cells should be considered only in the horizontal and vertical directions to form the paths. For example, when the player clicks on the cell highlighted in the figure to the left, the grid receives the colouring of the figure to the right. The goal of the game is to make the grid monochromatic.

Input Description

The first line of the input consists of 2 integers N and M (1 ≤ N ≤ 4, 1 ≤ M ≤ 5), which represent respectively the number of lines and the number of columns of the grid. The N lines following describe the initial configuration of the grid, representing each colour by an integer between 0 and 9. The input does not consist of any other line.

Output Description

Print a line containing a single integer that represents the minimum number of clicks that the player must do in order to make the grid monochromatic.

Input Sample

1:

4 5
01234
34567
67890
90123

2:

4 5
01234
12345
23456
34567

3:

4 5
00162
30295
45033
01837

Output Sample

1:

12

2:

7

3:

10

I'm trying to find a solution with backtracking (Because of the time limit of 8 seconds and small size of the grid). But it is taking time limit exceeded. Some people just made it on 0 secs.

There is some other algorithm to solve this ?

#include <stdio.h>
#include <string.h>

#define MAX 5
#define INF 999999999

typedef int signed_integer;

signed_integer n,m,mink;
bool vst[MAX][MAX];

signed_integer flood_path[4][2] = {
    {-1,0},
    {1,0},
    {0,1},
    {0,-1}
};

//flood and paint all possible cells... the root is (i,j)
signed_integer flood_and_paint(signed_integer cur_grid[MAX][MAX],signed_integer i, signed_integer j, signed_integer beta, signed_integer alpha, signed_integer colors[]){
    //invalid cell
    if (vst[i][j] || i < 0 || i >= n || j < 0 || j >= m)
        return 0;

    //mark existent colors
    colors[cur_grid[i][j]] = 1;

    //only alpha and beta colors counts
    if (cur_grid[i][j] != beta && cur_grid[i][j] != alpha)
        return 0;

    //mark (i,j) as visited and change its color
    vst[i][j] = true;
    cur_grid[i][j] = alpha;

    //floodit !
    signed_integer ret = 1;
    for (signed_integer k = 0; k < 4; k++)
        ret += flood_and_paint(cur_grid,i + flood_path[k][0], j + flood_path[k][1], beta, alpha, colors);

    //how many cells change
    return ret;
}

void backtrack(signed_integer cur_grid[MAX][MAX],signed_integer k,signed_integer _cont, signed_integer alpha) {
    //bigger number of clicks for this solution ? ... getting back
    if(k >= mink)
        return;

    signed_integer colors[10];
    memset(vst, false, sizeof(vst));
    memset(colors, 0, sizeof(colors));

    signed_integer beta = cur_grid[0][0];
    signed_integer cont = flood_and_paint(cur_grid, 0, 0, beta, alpha, colors);

    //there are alpha colors to change and no beta colors to change
    colors[alpha] = 1;
    colors[beta]  = 0;

    //all squares on same color
    if (cont == n * m) {
        mink = k;
        return;
    }

    //this solution is equals to another ? ... getting back
    if (cont == _cont)
        return;

    ++k;//new click

    //copy this matrix and backtrack
    signed_integer copy[MAX][MAX];
    for (signed_integer c = 0; c < 10; ++c){
        if (colors[c] && c != cur_grid[0][0]) {
            memcpy(copy, cur_grid,n*m*sizeof(signed_integer));
            backtrack(copy,k,cont,c);
        }
    }
}

void cleanBuffer(){
     while (getchar() != '\n');
}

int main(void) {
    signed_integer grid[MAX][MAX];
    scanf("%d %d",&n,&m);
    for (signed_integer i = 0; i < n; ++i) {
        cleanBuffer();
        for (signed_integer j = 0; j < m; ++j){
            grid[i][j] = getchar() - '0';
        }
    }
    mink = INF;
    backtrack(grid,0, 0, grid[0][0]);
    printf("%d\n",mink);
    return 0;
}

Answer 1

High level improvement

Note that the cells are either their original colour, or the last selected colour.

This means that we can represent the current state of the board by means of 20 bits (marking for each of the 4*5 cells whether they contain the original colour), and a number in the range 0 to 9 giving the last colour chosen.

This results in a maximum of 10 million states to explore. The backtracking function can avoid having to recurse if it reaches a state that has already been visited. I would expect this change to make your solution considerably faster.

Low level improvement

Representing the state by a 20bit mask and the last colour also makes the state a lot quicker to update and restore as only 2 numbers need to be changed instead of memcpy of the whole board.

Answer 2

If you think of the 4x5 board as "19 squares you can click on", that suggests there are 19! or 121,645,100,408,832,000 combinations to check. However, there are a number of optimisations that can drastically reduce the number of combinations to only a few dozen:

observations about the game strategy

• Clicking on different squares with the same colour has the same effect. So the board should be seen as "9 colours (or less) you can click on".
• Adjacent squares with the same colour should be seen as groups; they always act together. In the example below, the three white squares at the bottom right form such a group.
• It only makes sense to click on a colour that is adjacent to the corner group. In step one of the example below, only clicking on a pink, green, orange or white square makes sense.
• When several uniquely-coloured groups (where only one group has a certain colour) are adjacent to the corner group, the order in which they are clicked is unimportant. In the example below, after 5 and 3 have been clicked, any order of clicking 4, 7, 8 and 9 will have the same result.
• When all groups of a certain colour are adjacent to the corner group, they can be seen as uniquely-coloured groups; exactly one click per colour is needed to connect them. In the example below, after clicking 5 and 3, the two pink squares and the two green squares become two uniquely-coloured groups
• When the board has only uniquely-coloured groups, the number of necessary clicks equals the number of unconnected groups. In the example below, after clicking 5 and 3, exactly eight more clicks are necessary.
• If there is exactly one unconnected group that has the same colour as the corner group, and they are separated by more than one other group, the group can be seen as a uniquely-coloured group.
• Reducing the number of clicks means connecting several groups at once. This can be done when several same-coloured groups are adjacent to the corner group (as when clicking 1 or 2 in step 3 of the example below), or by clicking a group which separates the corner group from a group with the same colour (as happens in steps 1 and 2 in the example).

Algorithm based on optimal strategy

A recursive algorithm based on an optimal strategy using the rules listed above, goes through these steps for every recursion:

1. If only uniquely-coloured groups are left, the number of clicks equals the number of unconnected groups; return this number.
2. If a group with the same colour as the corner-group is separated from it by only one other group, click this other group and recurse. If several options exist, try all of them.
3. If one or more uniquely-coloured groups (or all groups of certain colours) are adjacent to the corner group, click them all in any order. Then re-evaluate the board from step 1.
4. Try clicking every colour adjacent to the corner group and recurse.

A Javascript implementation of a brute-force algorithm needed tens of millions of recursions for example 1 and 3 in the question, with an execution time far above the 8 second limit. After implementing the optimisations described above, example 1 was solved with just 38 recursions, and an execution time of a few milliseconds. Examples 2 and 3 were even quicker.