A*A方格着色的代码与问题

问题描述：给方阵平面图用4色着色。

 

关于这样的平面图着色的问题，我前天的想法就是这样的：

#include
#include

#define RANK 5
char colors[4] = {'B', 'G', 'R', 'Y'};
char up = 'N', left = 'N';
char color[RANK][RANK];

void show_color()
{
        int i,j;
        for(i = 0; i < RANK; i ++)
        {
                for(j = 0; j < RANK; j ++)
                        printf("%c", color[i][j]);
                printf("\n");
        }
        printf("========\n");

}

void set_color(char upC, char leftC, int row, int column)
{
        int i;
        int new_row, new_column;
        char new_upC, new_leftC;

        if(row == (RANK -1) && column == (RANK -1))
        {
                for(i = 0; i < 4; i ++)
                {
                        if(colors[i] == upC || colors[i] == leftC)
                                continue;
                        else
                        {
                                color[row][column] = colors[i];
                                show_color();
                        }
                }
                return;
        }
        for(i = 0; i < 4; i ++)
        {
                if(colors[i] == upC || colors[i] == leftC)
                        continue;
                else
                {
                        color[row][column] = colors[i];
                        if(column == (RANK -1)) //the last column
                        {
                                new_column = 0;
                                new_row = row +1;
                                new_upC = color[row][0];
                                new_leftC = 'N';
                        }
                        else
                        {
                                new_column = column + 1;
                                new_row = row;
                                if(row == 0)
                                        new_upC = 'N';
                                else
                                        new_upC = color[row - 1][column + 1];
                                new_leftC = color[row][column];
                        }
                        set_color(new_upC, new_leftC, new_row, new_column);
                }
        }
}

int main()
{
        set_color('N', 'N', 0, 0);
        return 0;
}

 

不过，我不打算再考虑下去了。

1*1， 4种解

2*2， 84

3*3， 9612

4*4， 6,000,732

...

我只能把问题做到这一步了，还有一点对以上代码的想法，考虑到其实你求出一种从R开始算的着色方法，把颜色替换，其它颜色开始算的结果也是一样的。但这对于整体的求解时间的减少，杯水车薪。