Как закрасить поле r x r n разными цветами, не используя один и тот же цвет в одном столбце, строке

Question

Недавно я столкнулся с этой проблемой и не могу ее решить из-за времени.

"Создайте программу, которая ответит, сколько способов нарисовать поле r by r разными цветами, не используя один и тот же цвет в одной строке и одном столбце".

Я написал для него код, но для ответа требуется более 30 минут, поле размером 6 на 6 с 6 цветами.

Итак, я подумал о многомерном запоминании, но у меня нет идеи добавить массив запоминания в мой код.

Пожалуйста, помогите мне сделать мой код быстрее или предложить новый способ.

#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

Это также пример обобщенной проблемы точного покрытия, класса задач, который включает в себя знакомые примеры, такие как головоломка Судоку (вы можете заметить сходство) и проблему N королев. Проблема является NP-полной, так что нет суперэффективного алгоритма, но есть каноническое решение, известное как Алгоритм X, благодаря Дональду Кнуту.

Чтобы перевести вашу задачу на язык точного покрытия, обратите внимание, что существуют ограничения r^2+2rn, которые должны быть выполнены ровно ноль или один раз: для строки и столбца 0 <= i,j