Другие языки программирования и технологии

Язык С. Помогите построить ортогональные латинские квадраты.

Здравствуйте. Мне дали такое задание:
Необходимо подсчитать количество латинских квадратов, ортогональных данному:
0572164938
6051298473
4867039215
1439807652
8324756091
7203941586
5610473829
9148625307
2795380164
3986512740

То есть, мне нужно написать программу на С, которая будет находить ортогональные квадраты.
Я пытался что-то сделать и пришел к выводу, что программа должна сразу генерировать квадраты ортогональными основному квадрату, вроде бы такой метод используется в народе, но как все это реализовать я не знаю. Да и формулу я найти не смог. Помогите пожалуйста!!
Michael Golubev
Michael Golubev
400
Такой вариант построения ортогональных квадратов.

#include <stdio.h>
#include <conio.h>

#define n 10
#define mask ~((-1) << n)
#define border (1 << n)

char s[n][n] = {{"0572164938"}, {"6051298473"}, {"4867039215"},
 {"1439807652"}, {"8324756091"}, {"7203941586"}, {"5610473829"},
 {"9148625307"}, {"2795380164"}, {"3986512740"}};

int q[n][n], a[n][n];
int p[n * n];
long long m = 0;

void solution(int, int);

int main()
{
 int i, j;
 for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
  {
   q[i][j] = 1 << (s[i][j] -= '0');
   a[i][j] = border;
  }
 solution(0, 0);
 printf("Ортогональных латинских квадратов: %d%09d\n", (int)(m / 1000000000), (int)(m % 1000000000));
 getch();
 return 0;
}

void solution(int i, int j)
{
 int k, t, r, v, set = 0;
 for (k = 0; k < i || k < j; k++)
  set |= a[i][k] | a[k][j];
 for (k = 1; (set & mask) != mask && !(k & border); k <<= 1)
  if (!(set & k))
  {
   v = q[i][j] << 2 * n | k;
   for (t = i * n + j - 1; t >= 0; t--)
    if (p[t] == v) break; // <========
   if (t < 0)
   {
    t = i;
    r = j >= n - 1? t++, r = 0 : j + 1;
    if (t >= n) m++;
    else
    {
     p[i * n + j] = v;
     a[i][j] = k;
     solution(t, r);
     a[i][j] = border;
    }
   }
  }
}

Для хотя бы какого-то ускорения, построение идет бинарными полями. Поэтому, если потребуется выводить полученные квадраты, придётся их предварительно декодировать.
Для порядков n = 3, 4, 5, 7 получено соответственно 6, 48, 360, 3200400 ортогональных квадратов. Для n = 8 за три часа ни одного не нашлось, и процесс ещё не завершился.

Попробуйте что-то здесь ещё оптимизировать, у меня мысли закончились.
При отладке выяснилось, что самое прожорливое по времени условие в цикле проверки ортогональности при генерации квадрата (помечено стрелкой).
Андрей Телегин
Андрей Телегин
51 590
Лучший ответ
Андрей Телегин Кстати, не к каждому латинскому квадрату можно подобрать ортогональный.
Андрей Телегин Если переписать подпрограмму так:

void solution(int i, int j)
{
 int k, t, r, set=0;
 for (k = 0; k < i || k < j; k++)
  set |= (1 << a[i][k]) | (1 << a[k][j]);
 for (k = 0; (set & mask) != mask && k < n; k++)
  if (!(set & (1 << k)) && p[q[i][j]][k] == 0)
  {
   t = i; r = j >= n - 1? t++, 0 : j + 1;
   if (t >= n) m++;
   else
   {
    p[q[i][j]][k]++;
    a[i][j] = k;
    solution(t, r);
    a[i][j] = n;
    p[q[i][j]][k]--;
   }
  }
}

то процесс ускоряется в несколько раз, но принципиально проблему не решает.
Davit Bznuni Сложно, да и откуда ты столько знаешь ?
Michael Golubev Эмм.... Извините, но я забыл упомянуть. Программа должна делать все это с помощью рекурсии, я вижу вас заинтересовало это задание, не могли бы вы мне помочь? Вот мой скайп Rustam19983. Мне очень нужна помощь, сам не справляюсь
#include
#include

#define n 10
#define mask ~((-1) << n)
#define border (1 << n)

char s[n][n] = {{"0572164938"}, {"6051298473"}, {"4867039215"},
 {"1439807652"}, {"8324756091"}, {"7203941586"}, {"5610473829"},
 {"9148625307"}, {"2795380164"}, {"3986512740"}};

int q[n][n], a[n][n];
int p[n * n];
long long m = 0;

void solution(int, int);

int main()
{
 int i, j;
 for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
  {
   q[i][j] = 1 << (s[i][j] -= '0');
   a[i][j] = border;
  }
 solution(0, 0);
 printf("Ортогональных латинских квадратов: %d%09d\n", (int)(m / 1000000000), (int)(m % 1000000000));
 getch();
 return 0;
}

void solution(int i, int j)
{
 int k, t, r, v, set = 0;
 for (k = 0; k < i || k < j; k++)
  set |= a[i][k] | a[k][j];
 for (k = 1; (set & mask) != mask && !(k & border); k <<= 1)
  if (!(set & k))
  {
   v = q[i][j] << 2 * n | k;
   for (t = i * n + j - 1; t >= 0; t--)
    if (p[t] == v) break; // <========
   if (t < 0)
   {
    t = i;
    r = j >= n - 1? t++, r = 0 : j + 1;
    if (t >= n) m++;
    else
    {
     p[i * n + j] = v;
     a[i][j] = k;
     solution(t, r);
     a[i][j] = border;
    }
   }
  }
}
Сергей Мавков
Сергей Мавков
152

Похожие вопросы