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

Question

最近遇到了这个问题，由于时间问题无法解决

'Make a program that answers how many ways to paint r by r field with n different colors, without using the same color at same row, same column.'

我编写了代码，但在只有 6 x 6 字段和 6 种颜色的情况下回答需要 30 多分钟。

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

请帮助我提高代码速度或提出新方法。

#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 problem, a class of problems that includes familiar examples like Sudoku puzzle (you can note the similarity) and the N queens problem. The problem is NP-complete so there isn't a super efficient algorithm, but there is a canonical solution known as Algorithm X 的示例，归功于 Donald Knuth。

要将您的问题翻译成精确覆盖的语言，请注意必须精确满足 r^2+2rn 次约束零次或一次：对于行和列 0 <= i,j < r，只有一个条目，并且对于每个 0 <= k < r 和 0 <= c < n，在行（或列）k 中有一个颜色为 c 的条目。 table 中有 nr^2 个可能的条目，即在第 i 行第 j 列放置一个颜色 c。这些中的每一个都满足两个约束（即颜色 c 和第 i 行，第 j 行的颜色 c）而不满足任何其他约束。因此，您可以构造一个具有 nr^2 行和 2rn 列的矩阵。仅解决此 table 的精确覆盖问题有点过于严格，因为它要求 n 种颜色中的每一种颜色在每行和每列中出现一次，而不是最多一次。这种差异使该问题成为广义精确覆盖问题，并通过添加 2rn 个簿记行来解决，每个记录行在对应于 row/column 颜色条件的 2rn 个约束中恰好有一个 1。

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

How to paint r x r field with n different colors without using same color at same column, row

c

algorithm

recursion

memoization