如何使用n种不同的颜色在同一列上使用相同的颜色绘制r x r字段

Question

最近，我遇到了这个问题，因为时间的推移我无法解决它。

'制作一个程序，可以通过r字段使用n种不同的颜色来绘制r的方式，而不会在同一行，同一列使用相同的颜色。

我编码为它，但它需要超过30分钟回答6只6乘6色的领域。

所以，我想到了多维memoization，但我没有想法在我的代码中添加memoization数组。

请帮我让我的代码更快或建议新的方式。

#include<stdio.h> 
#include<stdlib.h> 
int check[100][100], scheck[100][100], n, r; 
long long cnt; 
void arr(int x, int y) { 
    int i, k=0; 
    for (int j = 0; j < n; j++) { //about n colors 
     if (check[y][j] == 0 && scheck[x][j] == 0) { //if there is no j th color in same row and column 
     check[y][j] = 1; // check 'there is j th color in y th row, x th column 
     scheck[x][j] = 1; // to make same effect with inputing j at virtual field[y][x] 
     if (x == r - 1) { // if x th column is the end of right 
      if (y == r - 1) cnt++; // if y th column is the bottom, count this 
      else arr(0, y + 1); // else fill next row, first column 
     } 
     else arr(x + 1, y); // else fill next right square 
     check[y][j] = 0; // check 'there is no j th color in y th row, x th column 
     scheck[x][j] = 0; // to make same effect with erasing j virtual field[y][x] 
     } 
    } 
    return; 
} 
void main() { 
    printf("Input n, r (paint r x r field with n colors, same color cannot be used in same column and row) \n: "); 
    scanf("%d %d", &n, &r); 
    arr(0, 0); 
    printf("There are %ld ways to paint.\n", cnt); 
} 

Answer 1

这也是广义exact cover问题的一个例子，一类的问题，这些问题包括像数独题熟悉的例子（可以注意到相似性）和N后问题。这个问题是NP完全的，所以没有一个超高效的算法，但是由于Donald Knuth的原因，存在一个称为Algorithm X的规范解决方案。

要翻译您的问题到恰当覆盖的语言，注意，有R^2个+ 2RN约束必须严格满足零次或一次：行和列0 < = I，J < R，有只有一个条目，并且对于每个条目，在行（或列）k中具有颜色c的条目。表中有nr^2个可能的条目，即在第i行和第j列放置一个颜色c。它们中的每一个满足两个约束（即，颜色c和行i，行j处的颜色c），但不满足任何其他约束。因此，你可以构造一个有nr^2行和2rn列的矩阵。只为这个表格解决确切的封面问题有点过分限制，因为它要求每一行中每一种颜色出现一次，而不是最多一次。这种差异导致问题成为广义精确覆盖问题，并且通过添加2n个簿记行来解决这个问题，其中每个记录行在与行/列颜色条件相对应的2rn约束中的仅一个约束处具有1。