如何使用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。