Судоку: так скільки ж їх? Частина 2/2

Привіт Хабр!

Це друга частина перекладу статті про підрахунок різних судоку.



У цій частині ми поринемо в теорію груп, починаючи з самих основ, але зачіпаючи тільки те, що нам знадобиться для відповіді на питання: а скільки ж є дійсно різних судоку — без жодних повторів у вигляді поворотів, віддзеркалень і т. п. Ті, хто досить добре знайомий з теорією груп — ймовірно, знайдуть тут мало що цікавого. Для решти ж почитати дуже навіть корисно. На всяк випадок: я себе фахівцем з теорії груп не вважаю, що при перекладі статті я сам по суті вивчав її майже з нуля. Тобто, цілком можуть бути косяки — пишіть мені в лічку. З іншого боку — я для більшості визначень лазив у вікіпедію, а всі чисельні результати підтвердив власноруч написаною програмою. Так що, по ідеї, кількість косяків повинно прагнути до нуля. Але мало.

Як звичайно, мої коментарі виділені курсивом або заховані під спойлери. Під спойлерами можна знайти найцікавіше — шматки коду, які веріфіціруют всі числа, отримані в оповіданні.

Симетрії
Отже, у попередній частині статті ми порахували, що кількість різних сіток судоку одно N=6670903752021072936960≈6.671×1021. Але досить часто ми можемо отримати одну сітку судоку з іншої, застосовуючи прості перетворення. Наприклад, якщо у нас є коректно заповнена сітку судоку, то, повертаючи його на 90°, ми отримуємо іншу сітку, яка відрізняється від вихідної, але все ще залишається коректною. Насправді, ми можемо розглядати ці сітки як однакові, оскільки в результаті перетворення наша сітка — ще одне з рішень судоку. Аналогічно, якщо ми замінимо всі 3-ки в сітці на 4-ки, а всі 4-ки на 3-ки, то ми отримаємо іншу коректну сітку. Ми також могли б взяти якусь сітку судоку, поміняти місцями п'ятий та шостий рядки, і, врешті-решт, все одно отримати коректну сітку. Коли ми робимо такі перетворення, ми зберігає таку властивість сітки, як її коректність (У попередній частині статті ми робили щось дуже схоже, але тільки з частиною сітки — шпальтою. Тепер же ми граємося з усією таблицею 9×9. Важлива відмінність у тому, що зараз ми розглядаємо тільки такі перетворення, які можна застосувати до будь сітці (із збереженням коректності), тобто розглянута раніше операція свапания кутів прямокутника всередині сітки судоку не підходить, так як до деяких сіток вона застосовна, а до деяких — ні.).

Операції такого виду називаються симетріями. Симетрія об'єкта — це операція, яка зберігає деяку властивість об'єкта. Цікаво відзначити, що якщо ми застосовуємо до об'єкта одну симетрію, і відразу після цього — другу симетрію, то підсумкове перетворення буде ще однією симетрією. Операція, яка залишає об'єкт незмінним — це теж одна з симетрій. Для будь-якої симетрії існує інша симетрія, яка відкочує тому всі зміни, зроблені першої. І нарешті, якщо нам потрібно застосувати одну симетрію, потім другу, потім третю, ми можемо згрупувати або першу та другу симетрію разом, або другу і третю — і в результаті отримати одне і те ж перетворення.

Всі ці властивості свідчать про те, що безліч симетрій об'єкта формують групу. Група — це безліч G, разом з операцією ·, для якого виконуються наступні властивості:

  1. Якщо g і h — елементи G, то g·h — теж елемент G (Математики кажуть, що G замкнуто щодо операції ·).
  2. Якщо g, h і k — елементи G, то g·(h·k)=(g·h)·k (Це властивість операції групи називається асоціативністю).
  3. елемент e G такий, що g·e=e·g=g для всіх g з G (Цей елемент e називається нейтральним елементом групи G, так як він залишає кожен елемент G незмінним відносно операції).
  4. Для кожного елемента g з G існує інший елемент h G такий, що g·h=h·g=e, де e — нейтральний елемент (Елемент h називається оберненим елементом до g, позначається як g-1).
Зауважимо, що у визначеннях вище ми використовуємо мультиплікативну позначення для операції групи. Ми могли б використовувати адитивну нотацію, і в цьому випадку зворотний елемент для g позначався б -g. (Мультиплікативну нотація — це ніби наша операція «помножити», а адитивна — «додати»).

Вправа Перевірте, що множина цілих чисел Z з операцією складання — група. Для цього потрібно перевірити виконання всіх чотирьох властивостей.

Група цілих чисел має ще одну дуже цікаву властивість: порядок складання чисел абсолютно не важливий. Тобто, для будь-яких двох цілих чисел a і b, a+b — це те ж саме, що і b+a. Коли операція групи задовольняє цій властивості (це властивість називається комутативність), група називається абелевой.

Давайте розглянемо приклад групи симетрій, наприклад, квадрат з пронумерованими кутами:



Для цього геометричного об'єкта є вісім перетворень, які зберігають той факт, що це — квадрат. Іншими словами, у квадрата вісім симетрій. Всі вони — різні повороти і відображення разом з операцією композиції перетворень:

  1. Поворот на 0 градусів (нейтральний елемент).
  2. Поворот на годинниковою стрілкою на 90 градусів.
  3. Поворот на годинниковою стрілкою на 180 градусів.
  4. Поворот на годинниковою стрілкою на 270 градусів.
  5. Відображення відносно горизонтальної осі, яка проходить через центр квадрата).
  6. Відображення відносно вертикальної осі, яка проходить через центр квадрата).
  7. Відображення по-діагоналі з лівого нижнього кута в правий верхній.
  8. Відображення по-діагоналі з верхнього лівого кута в правий нижній.
Вправа Виберіть якісь два перетворення зі списку вище і перевірте, що застосування одного з них, а потім іншого — це теж перетворення, яке вже є в цьому списку. Чи Можете ви знайти два таких перетворення, що приводять до різних результатів в залежності від порядку їх застосування?

На відміну від групи цілих чисел, група симетрій квадрата неабелева.

Група симетрій G коректної сітки судоку містить всі перетворення квадрата і, крім цього, деякі інші перетворення зразок переміщення блоків, рядків і стовпців, а також композиція всіх цих перетворень. Таким чином, група симетрій породжується перетвореннями наступних видів:

  1. Перепризначення дев'яти цифр.
  2. Перестановка трьох стеків.
  3. Перестановка трьох смуг.
  4. Перестановка трьох стовпців у якому-небудь стеку.
  5. Перестановки трьох рядків в будь-якій смузі.
  6. Всякі відображення і повороти (зі списку симетрій квадрата).
Важливе зауваження: це не список всіх елементів G! Це список різноманітних групи симетрій, і комбінуючи їх усіма різними способами ми можемо отримати всі інші елементи групи. І конкретні перетворення всіх описаних вище типів, і будь-яка композиція, яка відрізняється від цих конкретних «базових» перетворень — всі вони включаються в групу симетрій G. Наприклад, один з елементів G — це обмін першої та другої рядків, конкретне перетворення типу (5). Нехай X — множина всіх коректних сіток судоку. Ми знаємо, що це безліч з кінцевого числа елементів. З того, що кожен елемент G — це деяка відповідність, яка відображає одну із сіток на іншу (насправді воно відображає всі сітки на якісь інші, тобто це деяка перестановка всіх елементів X), ми можемо укласти, що G теж включає в себе тільки кінцеве число елементів-симетрій.

Ми називаємо дві сітки судоку еквівалентними, якщо ми можемо перетворити одну з них в іншу застосувавши одну або більше симетрій з G. Якщо ні одна з послідовностей симетрій не перетворює одну із сіток в іншу, то ми такі сітки називаємо істотно різними.

Це відношення дійсно є відношенням еквівалентності у формальному математичному сенсі, оскільки воно задовольняє наступним трьом властивостям:

  1. Сітка A еквівалентна самої себе (це властивість називається рефлективністю).
  2. Якщо A еквівалентна B, то B еквівалента A (ця властивість називається симетричністю).
  3. Якщо A еквівалентна B, а B еквівалентна C, то A еквівалентна C (ця властивість називається транзитивностью).
Для будь коректної сітки судоку A ми можемо розглядати всі сітки, еквівалентні A, як дійсно точно такі ж, як A. Якщо ми згрупуємо всі разом сітки, які еквівалентні один одному, то ми, насправді, розіб'ємо множину всіх сіток на непересічні частини: справді, X буде розбито на такі підмножини, що ніякі дві з них не мають спільних елементів. Математики називають такі підмножини класами еквівалентності. Будь-які два елементи з одного класу еквівалентності еквівалентні один одному по якій-небудь симетрії з G. Безліч класів еквівалентності позначається як X/G і читається як «X за модулую G» або «X mod G» (ще математики називають X/G фактор-множиною).

У попередній частині статті ми задавалися питанням про кількість різних сіток судоку без всяких симетрій, і було б цікаво знайти число істотно різних сіток. Згідно з міркуванням, викладених вище, загальна кількість класів еквівалентності, або число елементів у X/G — це і є ні що інше, як кількість істотно різних сіток судоку. Далі ми розглянемо метод, який на початку 2006 року використовували Ед Расселл (Ed Russell) і Фразер Джарвіс (Frazer Jarvis) для обчислення цього числа.

Спочатку ми трохи обделим увагою операцію перепризначення чисел і розглянемо тільки ті симетрії, які щось роблять саме з сіткою — з усією сіткою, з блоками або з окремими осередками. Розглянемо ці симетрії — їх типи (2)-(6) в списку вище — і їх композиції. Ці симетрії дають нас групи H, в якій Расселл і Джарвіс нарахували рівно 3359232 різних симетрій. Іншими словами, H — це група, яка породжується симетріями типів (2)-(6).

КоментарВ будь незрозумілої ситуації починай варити мет писати код. Ось і зараз абсолютно незрозуміло звідки береться число 3359232. Тому давайте почнемо писати код для того, щоб перевірити, що у групи H рівне 3359232 різних симетрій.

Почнемо зі структури, яка описує симетрії групи. теорема Келі, будь-яка кінцева група ізоморфна підгрупі деякої симетричною групи. Якщо говорити зрозумілою мовою, то будь-яку кінцеву групу можна представити у вигляді деякої системи перестановок. Ось і для групи H ми використовуємо перестановку довжини 81 — по одному елементу перестановки на кожну клітинку судоку.
struct SYMMETRY
{
unsigned char m[9][9];

void print()
{
for (int i=0; i<9; i++)
{
for (int j=0; j<9; j++)
printf( "%2d ", (int)m[i][j] );
printf( "\n" );
}
printf( "\n" );
}

static SYMMETRY E()
{
SYMMETRY re;
unsigned char t = 0;
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)
re.m[i][j] = t++;
return re;
}

static SYMMETRY swap_stacks( int i, int j )
{
SYMMETRY re = SYMMETRY::E();
for (int a=0; a<9; a++)
for (int b=0; b<3; b++)
swap( re.m[a][i*3+b], re.m[a][j*3+b] );
return re;
}

static SYMMETRY swap_columns( int s, int i, int j )
{
SYMMETRY re = SYMMETRY::E();
for (int a=0; a<9; a++)
swap( re.m[a][s*3+i], re.m[a][s*3+j] );
return re;
}

static SYMMETRY rotate()
{
SYMMETRY re = SYMMETRY::E();
for (int a=0; a<5; a++)
for (int b=0; b<4; b++)
{
unsigned char tmp = re.m[a][b];
re.m[a][b] = re.m[8-b][a];
re.m[8-b][a] = re.m[8-a][8-b];
re.m[8-a][8-b] = re.m[b][8-a];
re.m[b][8-a] = tmp;
}
return re;
}

SYMMETRY multiply( SYMMETRY g )
{
SYMMETRY re;
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)
re.m[i][j] = g.m[m[i][j]/9][m[i][j]%9];
return re;
}

SYMMETRY inverse()
{
SYMMETRY re;
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)
re.m[m[i][j]/9][m[i][j]%9] = i*9+j;
return re;
}
};

Тобто в кожній позиції таблиці 9x9 ми зберігаємо номер позиції, в яку перейде елемент поточної позиції після застосування симетрії. Зверніть увагу — симетрія нічого не знає про те, які числа в судоку зараз знаходяться. У наведеному вище коді прописані створення таких симетрій, як нейтральний елемент, перестановка стеків, перестановка стовпців і поворот на 90 градусів.

Вправа Покажіть, що все симетрії типів (2)-(6) можна отримати композицією тих симетрій, які ми реалізували в коді.

Далі в коді йде реалізація композиції або множення симетрій. В кінці додано реалізація знаходження оберненого елемента (вона нам поки не потрібна, але знадобиться пізніше).

Тепер на основі наявних симетрій давайте породимо всю групу H:
bool operator== (const SYMMETRY & A, const SYMMETRY & B)
{
for (int a=0; a<9; a++)
for (int b=0; b<9; b++)
if (A. m[a][b] != B. m[a][b])
return false;
return true;
}

bool operator< (const SYMMETRY & A, const SYMMETRY & B)
{
for (int a=0; a<9; a++)
for (int b=0; b<9; b++)
if (A. m[a][b] != B. m[a][b])
return A. m[a][b] < B. m[a][b];
return false;
}

set< SYMMETRY > Set;
queue< SYMMETRY > Q;

void bfs_push( SYMMETRY G )
{
if (Set.find( G ) != Set.end()) return;
Set.insert( G );
Q. push( G );
if (Set.size()%100000==0) fprintf( stderr, "G. sz=%d\n", (int)Set.size() );
}

void find_all_elements_of_group()
{
Q. push( SYMMETRY::E() );
Set.insert( SYMMETRY::E() );
while (Q. size()>0)
{
SYMMETRY G = Q. front();
Q. pop();
bfs_push( G. multiply( SYMMETRY::rotate() ) );
for (int i=0; i < 3; i++)
for (int j=i+1; j < 3; j++)
{
bfs_push( G. multiply( SYMMETRY::swap_stacks(i,j) ) );
for (int k=0; k<3; k++)
bfs_push( G. multiply( SYMMETRY::swap_columns(k,i,j) ) );
}
}

printf( "sudoku group size %d\n", (int)Set.size() );
fprintf( stderr, "sudoku group size %d\n", (int)Set.size() );
}

Оператори для порівняння і визначення який елемент менше потрібні чисто для того, щоб set міг коректно виконувати свої операції (а інакше він навіть відмовиться компілюватися). Далі, ми реалізуємо обхід групи симетрій H за допомогою обходу в ширину (можна було б використовувати і обхід в глибину, але він з'їдає дуже багато пам'яті на стеку рекурсії).

Більш детально: спочатку ми поміщаємо в чергу Q нейтральну симетрію. Після цього виймаємо і обробляємо симетрії, поки вони в черзі не закінчаться. Обробки йде наступним чином: ми тільки що витягнуту з черги симетрію множимо на всі доступні нам «базові» симетрії. Безліч Set виконує роль масиву прапорів і зберігає в собі всі отримані на поточний момент симетрії. Якщо після множення, ми отримали нову симетрію — таку, що її немає у Set — то ми запам'ятовуємо її в безлічі Set і поміщаємо в кінець черги Q. Якщо після множення ми виявляємо, що нова симетрія насправді вже є у Set — ми нічого не робимо, так як ми вже обробляли цю симетрію раніше.

В результаті В кінці виконання алгоритму у Set скопятся всі симетрії з групи H (взагалі, якщо говорити строго — там скопятся всі перестановки якоїсь групи P, яка ізоморфна групі H, але ми не будемо чіплятися з цього приводу). Запуск коду підтверджує, що в H дійсно рівно 3359232 елементів.

До речі, в структурі SYMMETRY у кожного елемента перестановки не дарма обраний тип unsigned char. В процесі обчислення ми зберігаємо в множині Set і в черзі Q мільйони об'єктів (які важать на 80 байт), тому потрібно бути готовим до того, що програма буде споживати близько 450Мб пам'яті в процесі обчислень і близько 300Мб в кінці, коли черга спорожніє.


Коментардо Речі, а як можна уявити собі у вигляді групи перестановок групу, яка породжується симетріями всіх типів (1)-(6)? Перестановки — вони ж дурні, вони не дивляться на те, які числа записані у судоку. Вони тупо перемішують елементи не вникаючи в суть.

Для того, щоб врахувати симетрії типу (1), ми трохи трансформуємо сітку судоку. А саме: переведемо її в 3D (як би дивно це не звучало). Уявіть собі куб 9x9x9, на який зверху спроецирована наша сітка судоку. Тобто, на кожну клітинку судоку доводиться стовпець з 9 одиничних кубиків у великому кубі. Ну і тепер для кожного стовпця ми робимо наступне: якщо у відповідній клітинці судоку знаходиться число i, то ми фарбуємо i-ий (рахуючи зверху) кубик стовпця в чорний колір, а всі інші кубики — в білий. В результаті ми отримаємо куб, кожен з 729 кубиків якого пофарбований в один з двох кольорів (чорний або білий), причому в кожному стовпці в чорний колір пофарбований рівно один кубик. Ну і тепер всі симетрії типів (2)-(6) — це перемішування стовпців куба, в той час як симетрії типу (1) — це перемішування горизонтальних шарів цього куба.

Вуаля — ми висловили групу симетрій, породжувану симетріями типів (1)-(6) через підгрупу групи перестановок порядку 729.

Тепер наше поняття еквівалентності двох сіток можна визначити наступним чином: сітка A еквівалентна сітці B якщо ми можемо сітку A перетворити симетріями з групи H в деяку сітку C, таку, що в C можна перепризначити числа так, що в підсумку вийде сітка B. Ми можемо сказати, що A H-еквівалентна C, C эквиватентна B за перепризначення. Зауважимо, що H-еквівалентність та еквівалентність за перепризначення — це дійсно відношення еквівалентності (обидві вони задовольняють трьом властивостям зі списку вище).

Ми вважаємо, що H діє на безліч коректних сіток судоку X наступним чином: кожен елемент h з H являє собою відображення X на X, тобто переводить кожну з сіток з X в іншу (можливо ту ж саму сітку з X. Іншими словами, h дає нам спосіб перетворення будь коректної сітки в іншу коректну сітку, і кожен елемент h з H дає нам таке відображення.

Для будь-якої симетрії з h з H ми можемо розглянути ті сітки, які h залишає на місці з точністю до перепризначення. Ми маємо на увазі всі такі сітки A, що якщо ми застосуємо до A симетрію h і отримаємо сітку B, то B буде еквівалентна A за перепризначення (Такі об'єкти ще називаються нерухомими точками щодо елемента h). Так ми враховуємо той факт, що ми не врахували перепризначення в групі симетрій H.

КоментарДля кращого розуміння суті виразу «з точністю до перепризначення» слід прийняти той факт, що іноді безліч об'єктів, на яких ми застосовуємо всякі симетрії, можуть після застосування симетрії додатково самоподкручиваться до якогось нормального виду.

Ще один варіант для поліпшення розуміння: краще замість множини X всіх сіток судоку розглянути множину Y — множина всіх класів еквівалентності X щодо еквівалентності за перепризначення. Тобто кожен елемент Y — це кількість з 9! сіток судоку, які переходять один в одного при перепризначенні чисел (я взагалі кожен з цих елементів уявляю собі як прозору сферу, в якій плавають 9! окремих паперових сіток судоку). І коли ми застосовуємо до елемента y з Y елемент h з H — ми трансформуємо відразу все сітки судоку всередині y згідно з симетрією h. І в результаті отримуємо нове безліч сіток y' (а безлічі, як ви знаєте, порівнюються без урахування порядку елементів в них).

Слід зазначити, що самоподкручивание не суперечить теоремі Келі — вона для самої групи, а не для безлічі, на яке ми намагаємося цією групою діяти. Ми можемо діяти групою на дуже різні множини: навіть на безлічі з одного або двох елементів, навіть на іншу групу. Головне, щоб безліч, на яке ми діємо, задовольняло невеликому списком властивостей.

Для того, щоб порахувати кількість істотно різних сіток судоку, нам потрібна теорема теорії груп, під назвою лемма Бернсайда.

Лемма Бернсайда Нехай G — кінцева група, яка діє на множині X. Для кожного елемента g з G, нехай Xg позначає множина елементів X, які елемент g залишає на місці. Тоді кількість елементів у множині X/G одно |X/G|=1/|G|Σg in G|Xg|, де |-| — кількість елементів у множині.

Вправа Уявіть квадрат, в якому кожне з ребер розфарбоване в один з двох кольорів — синій або зелений. Дві розмальовки назвемо істотно однаковими, якщо існує така симетрія квадрата, що переводить першу з цих розмальовок у другу. Використовуйте лемму Бернсайда для того, щоб визначити кількість істотно різних розфарбувань. (Для кожної з восьми симетрій квадрата порахуйте кількість розмальовок, які не змінюються при застосуванні симетрії. Для кращого розуміння того, що відбувається можна намалювати все 24=16 розмальовок квадрата і уявити собі, як вони переходять один в одного. Лемма Бернсайда говорить нам, що для отримання відповіді потрібно скласти кількість не змінюються розмальовок для кожної симетрії і потім розділити отриману суму на кількість симетрій.)

У нашому ж випадку, кінцева група H діє на безліч X всіляких коректних сіток судоку. Для кожного h з H, ми хочемо знайти кількість таких елементів X, що вони не змінюються при застосуванні h з точністю до перепризначення чисел. Потім нам потрібно скласти всі ці числа і розділити їх на число елементів у H. І в результаті вийде відповідь — кількість істотно різних доби судоку. Тобто, нам потрібно взяти середнє арифметичне від кількості незмінних сіток (з точністю до перепризначення) по всіх елементах H.

Наприклад, коректна наступна сітка судоку є нерухомою точкою для повороту на 90° за годинниковою стрілкою (знову ж, з точністю до перепризначення чисел):



Вправа Визначте як перепризначити числа в оберненій сітці вище так, щоб вона збіглася з початковою. Випишіть всі числа від 1 до 9 і подивіться куди переходить число 1, потім куди переходить число 2, потім 3, ну і так далі. Загалом, переконайтеся, що ця сітка — нерухома точка для даної симетрії повороту.

Для того, щоб застосувати лемму Бернсайда (щоб обчислити кількість істотно різних сіток), ми могли б обчислити кількість нерухомих точок для кожного з 3359232 елементів H. Але, виявляється, деякі з цих 3359232 перетворень мають одне і те ж число невідмінюваних сіток! Расселл і Джарвіс використовували спеціальну програму GAP і визначили, що всі елементи H розпадаються на 275 класів симетрій таких, що будь-які дві симетрії з одного класу мають одне і те ж число незмінних сіток, і кожна симетрія з H має стільки ж нерухомих точок, скільки елемент одного з цих класів (знайомий процес, чи не правда?). Тому нам потрібно просто порахувати кількість фіксованих точок тільки для однієї симетрії з кожного з 275 класів. Знаючи скільки симетрій знаходиться в кожному з класів, ми потім зможемо дізнатися середнє, як в лемі Бернсайда.

КоментарЗ абзацу вище зовсім не ясно, як Расселл і Джарвіс отримали 275 класів. І взагалі, що за класи взагалі? Але, якщо заглибитися в їх оригінальну статтю (а не той научпоп, переклад якого ви читаєте), то можна зрозуміти, що мова йде про класах спряженості.

Інформація з википедии: елементи g1 g2 групи G називаються спряженими, якщо існує елемент h G, для якого h·g1·h-1 = g2.

Вправа Покажіть, що відношення спряженості є відношенням еквівалентності (три властивості з визначення еквівалентності по тексту вище вам в допомогу).

Вправа Покажіть, що якщо два елемента g1 g2 групи G пов'язані (причому h·g1·h-1 = g2 для деякого h з H), то у них однакову кількість нерухомих точок. Вказівка: покажіть, що для будь-якої нерухомої точки x X g1 об'єкт y=x·h-1 (теж X) є нерухомою точкою для g2, а для кожної нерухомої точки y X для g2 об'єкт x=y·h X — нерухома точка для g1. В результаті між нерухомими точками обох симетрій побудується биекция.

Отже, з теорією розібралися, тепер потрібно розібратися з практикою. А з нею не все так просто. Нам, по суті, треба для кожного елемента g з H перебрати інший елемент h з H, після чого побудувати зв'язок між g і h·g·h-1. А в кінці подивитися на компоненти зв'язності. Тільки от порядок групи H у нас під 3 мільйона і в лоб ми будемо будувати зв'язки до кінця століть (ну, принаймні, до кінця цього року точно). Тому ми вчинимо хитріше.

Давайте для початку в якості h брати не всі симетрії, а тільки дуже невелика їх підмножину. Наприклад, безліч симетрій, з яких ми в одному з минулих спойлерів породжуємо групи H. В результаті всі елементи H згруповано в часткові класи еквівалентності, їх стане набагато менше, і ми вже дообъединяем їх по-доброму.

map< SYMMETRY, int > classes;
SYMMETRY cur_g;
set< SYMMETRY > Set2;

void dfs1( SYMMETRY g, vector< SYMMETRY > & ops )
{
if (Set2.find( g ) != Set2.end()) return;
Set2.insert( g );
classes[cur_g]++;

for (int i=0; i<(int)ops.size(); i++)
dfs1( ops[i].multiply(g).multiply( ops[i].inverse() ), ops );
}

void find_conjugacy_classes()
{
vector< SYMMETRY > ops;
ops.push_back( SYMMETRY::rotate() );
for (int i=0; i < 3; i++)
for (int j=i+1; j < 3; j++)
{
ops.push_back( SYMMETRY::swap_stacks(i,j) );
for (int k=0; k<3; k++)
ops.push_back( SYMMETRY::swap_columns(k,i,j) );
}

int ind = 0;
for (set< SYMMETRY >::iterator it = Set.begin(); it != Set.end(); it++)
if (Set2.find( *it ) == Set2.end())
{
cur_g = *it;
dfs1( *it, ops );
printf( "M[%d]=%d\n", ind, classes[cur_g] );
fprintf( stderr, "M[%d]=%d\n", ind, classes[cur_g] );
ind++;
}

Set2.clear();
printf( "number of classes after step 1 %d\n", (int)classes.size() );
fprintf( stderr, "number of classes after step 1 %d\n", (int)classes.size() );
}

Асоціативний масив classes зберігає представника кожного класу, а також кількість елементів у кожному класі. Безліч Set2 — це масив прапорів, на зразок безлічі Set, який ми використовуємо для потреб поточного перебору, а в самому кінці очищаємо. Генерація класів відбувається наступним чином: спочатку ми всі «базові» симетрії складаємо в масив ops, після чого, починаючи з ще не розглянутого елемента, рекурсивно ходимо по графу сопряженностей з допомогою обходу в глибину і будуємо клас спряженості. Після цього ми беремо наступну ще не розглянуту симетрію, знаходимо клас для нього, і так далі.

Даний код (разом з попереднім) вже споживає на піку порядку 900Мб пам'яті, з яких близько 256Мб припадає на стек рекурсії (можна було б знову цей момент реалізувати як обхід в ширину, але в даному випадку обхід в глибину виявився не настільки ненажерливим по пам'яті — так що терпимо).… В результаті ми отримуємо шукані 275 класів.

Везіння? Ми ж ще недообработали наш результат. Насправді, дообрабатывать нічого не треба і ми дійсно отримали правильне розбиття на класи (це можна було б довести ще до запуску). Міркування про коректність нашого алгоритму виглядають приблизно наступним чином:

Розглянемо які-небудь зв'язані симетрії g1 g2, тоді існує симетрія h, для якої g2 = h·g1·h-1. При цьому, h можна представити у вигляді композиції симетрій, скажімо h = a·b·c, де a,b,c — це якісь «базові» симетрії. Тоді g2 = h·g1·h-1 = (a·b·c)·g1·(a·b·c)-1 = a·b·c·g1·c-1·b-1·a-1 = (a·(b·(c·g1·c-1)·b-1)·a-1). Тобто, з симетрії g1 ми б у нашому алгоритмі перейшли до симетрії p1=c·g1·c-1, від p1 — p2=b·g1·b-1, а від p2 — до a·g1·a-1=g2. Звідси отримуємо, що алгоритм коректний.

Вправа Розгляньте відображення сітки судоку відносно горизонтальної осі, що проходить через центр сітки, тобто через п'ятий рядок. Зауважимо, що п'ята рядок після відображення залишиться незмінною. Ви Можете перепризначити числа відображеної сітці так, щоб вона збіглася з початковою? І що можна сказати про нерухомих точках для відображення відносно горизонтальної осі? Тут взагалі є сітки, які не змінюються? (Згадайте той факт, що ми зараз розглядаємо якусь коректну сітку судоку, і в п'ятому рядку знаходяться всі дев'ять чисел).

Як можна бачити з вправи вище, H бувають такі симетрії, для яких немає нерухомих точок. Расселл і Джарвіс з подивом виявили, що насправді аж 248 класів з 275 містять симетрії, для яких немає жодної фіксованої точки. Так що їм залишилося тільки порахувати кількість незмінних сіток для симетрій з 27 решти класів і знайти скільки симетрій міститься у кожному з цих класів перед тим, як використовувати лемму Бернсайда. Вони написали програму, яка робить останні обчислення і в результаті отримали число 5472730538≈5.473×109 — кількість істотно різних сіток судоку.

КоментарМи наближаємося до найскладнішої ділянки коду — кодом підрахунку кількості нерухомих точок для кожного з 275 класів симетрій. І багато складності вносить саме той факт, що ми розглядаємо об'єкти, еквівалентні за перепризначення чисел — отакі узагальнені повністю заповнені сітки судоку. Всього їх 6670903752021072936960/9! = 18383222420692992 (це те саме число всіх сіток судоку, поділена на кількість варіантів, які виходять шляхом перепризначення чисел). Позначимо безліч таких узагальнених сіток як Y.

Отже, завдання для рішення: нам треба за деякою симетрії g порахувати кількість нерухомих точок з множини Y (всього таких підзавдань 275). Що відбувається з кожною нерухомою точкою при застосуванні g? Числа в сітці судоку змінюються місцями у відповідності з деякою перестановкою, потім йде перепризначення чисел, і після цього ми отримуємо початкову сітку. І той факт, що числа якось переназначаются, створює складність при побудові перебору. Однак, зауважимо, що якщо якась сітка є нерухомою точкою для якогось одного перепризначення, то для всіх інших перепризначень вона не є нерухомою точкою. Тому ми можемо перебрати всілякі перепризначення, знайти для кожного з них кількість нерухомих точок, а потім все скласти.

Виходить тепер нам треба вирішувати таку подподзадачу: дані симетрія g і перепризначення чисел h, треба для них порахувати кількість нерухомих точок з Y. Тепер розглянемо яку-небудь нерухому точку y з Y, а конкретно — число p у якійсь клітинці (i,j). При застосуванні g до y, (i,j) переходить у деяку позицію (i',j')=(i,j)·g, в якій, згідно перепризначення h, буде число q=p·h. Так як кінцева сітка дорівнює початкової, то число q має стояти в початковій сітці у позиції (i',j').

Тобто, відбувається наступне. g — це деяка перестановка сітки судоку, яку можна розбити на цикли. Наприклад, при симетрії повороту на 90 градусів, в цій перестановці буде знаходитися цикл (1,1)->(1,9)->(9,9)->(9,1)->(1,1) довжини 4. h — це теж певна перестановка, але вже просто з 9 чисел. І там теж все розпадається на цикли. Наприклад, там може бути цикл 2->3->2 довжини 2. І тепер, якщо ми хочемо в позицію (1,1) поставити 2, то (1,9) ми зобов'язані поставити 3, (9,9) — 2, а в (9,1) — 3. Далі цикл замикається. Зауважимо, що якщо довжина циклу в сітці судоку не ділиться на довжину циклу в перепризначенні — то ми не можемо в даний цикл в судоку записати жодне число з циклу перепризначення, оскільки в самому кінці у нас цикл «не замкнеться».

Тепер нам потрібно просто реалізувати перебір, в якому операція присвоювання числа клітинці сітки судоку додатково належним чином розставляє потрібні числа по всьому циклу (ну і паралельно перевіряє, що ніде не порушилося Головне Правило).

Давайте почнемо зі структури, яка ініціалізує себе і для кожного елемента сітки прораховує довжину циклу, в який цей елемент входить (ну і ще вважає деякі речі по дрібниці):
struct MEGAGRID
{
int T[9][9];
bool R[9][10], C[9][10], B[9][10];

int S[9][9]; // symmetry перестановок
int s_cycle[9][9]; // length of cycle for every element

int M[10]; // mapping перестановок
int m_cycle[10]; // length of cycle for every element

void init( SYMMETRY sym )
{
for (int a=0; a<9; a++)
for (int b=0; b<9; b++)
S[a][b] = sym.m[a][b];
memset( s_cycle, 0, sizeof( s_cycle ) );
for (int a=0; a<9; a++)
for (int b=0; b<9; b++)
if (s_cycle[a][b] == 0)
{
int cycle_len = 0;
int i = a, j = b;
while(1)
{
int tmp = S[i][j];
i = tmp/9;
j = tmp%9;
cycle_len++;
if (i==a && j==b) break;
}
while(1)
{
s_cycle[i][j] = cycle_len;
int tmp = S[i][j];
i = tmp/9;
j = tmp%9;
if (i==a && j==b) break;
}
}

for (int a=1; a<10; a++)
M[a] = a;
for (int a=1; a<10; a++)
m_cycle[a] = 1;
}

bool next_perm()
{
if (!next_permutation( M+1, M+10 )) return false;

memset( m_cycle, 0, sizeof( m_cycle ) );
for (int a=1; a<=9; a++)
if (m_cycle[a] == 0)
{
int cycle_len = 0;
int i = a;
while(1)
{
i = M[i];
cycle_len++;
if (i==a) break;
}
while(1)
{
m_cycle[i] = cycle_len;
i = M[i];
if (i==a) break;
}
}

return true;
}

void clear()
{
memset( T, 0, sizeof( T ) );
memset( R, 0, sizeof( R ) );
memset( C, 0, sizeof( C ) );
memset( B, 0, sizeof( B ) );
}
} G;

Процедура init() зберігає структуру поточну симетрію, і знаходить для неї всі цикли. Крім того, init() скидає поточне перепризначення до нейтрального. Процедура next_perm() дозволяє перерахувати всілякі перепризначення і для кожного з них знаходить всі цикли в перепризначенні. Процедура clear() видаляє всі клітинки в сітці T, яку ми пытаемя побудувати.

Тепер додамо нашій структурі методи для того, щоб можна було записувати і видаляти числа:
struct MEGAGRID
{
/* old code */

bool set_num( int num, int x, int y )
{
int n0=num, x0=x, y0=y;
if (s_cycle[x][y] % m_cycle[num] != 0) return false;
int L = s_cycle[x][y];
for (int a=0; a<L; a++)
{
if (R[x][num] || C[y][num] || B[(x/3)*3+(y/3)][num])
{
if (a>0) unset_num( n0, x0, y0, a ); // undo changes
return false;
}

T[x][y] = num;
R[x][num] = true;
C[y][num] = true;
B[(x/3)*3+(y/3)][num] = true;

int tmp = S[x][y];
x = tmp/9;
y = tmp%9;
num = M[num];
}

return true;
}

void unset_num( int num, int x, int y, int sz=0 )
{
int L = s_cycle[x][y];
if (sz!=0) L = sz;
for (int a=0; a<L; a++)
{
T[x][y] = 0;
R[x][num] = false;
C[y][num] = false;
B[(x/3)*3+(y/3)][num] = false;

int tmp = S[x][y];
x = tmp/9;
y = tmp%9;
num = M[num];
}
}
} G;

Процедура set_num() намагається привласнити потрібні значення по всьому циклу, в разі невдачі — всі зміни відкочуються. unset_num() ж відкочує зміни. Зазначимо, що set_num() у випадку невдачі використовує unset_num() для скасування змін, використовуючи «прихований» параметр, щоб скасувати зміни не по всьому циклу, а тільки за зміненою його частини.

В принципі, вже можна було б почати писати сам перебір, але, забігаючи вперед, скажу, що він буде тормознутый і в нього треба буде додати трохи відсікань. Яких? Давайте згадаємо останню вправу прямо перед цим спойлером. Там розглядалися симетрії, які не змінювали щось у сітці: рядок, стовпець або блок. Якщо ж у сітці щось з цього списку не змінюється, то єдине перепризначення чисел, яке до даної сітці можна застосувати, — це нейтральне перепризначення, тобто те, що не перемішує числа. Для цього перепризначення можна додати наступну евристику: якщо в перестановці сітки яка-небудь з комірок переходить в інший клітинку у стовпці або блоці або тій же рядку, то тоді для цього випадку загальна кількість нерухомих точок дорівнює нулю.

Так що давайте додамо до нашої структури ще і ці дві евристики:
struct MEGAGRID
{
/* old code */

bool is_immovable()
{
for (int a=0; a<9; a++)
{
bool flag = true;
for (int b=0; b<9; b++)
if (S[a][b] != a*9+b)
flag = false;
if (flag) return true;
}

for (int b=0; b<9; b++)
{
bool flag = true;
for (int a=0; a<9; a++)
if (S[a][b] != a*9+b)
flag = false;
if (flag) return true;
}

for (int a=0; a<3; a++)
for (int b=0; b<3; b++)
{
bool flag = true;
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
if (S[a*3+i][b*3+j] != (a*3+i)*9+b*3+j)
flag = false;
if (flag) return true;
}

return false;
}

bool has_bad_cycle()
{
for (int a=0; a<9; a++)
for (int b=0; b<9; b++)
{
int x = S[a][b]/9, y = S[a][b]%9;
if (!(x==a && y==b))
if (x==a || y==b || (x/3)*3+(y/3)==(a/3)*3+(b/3))
return true;
}
return false;
}
} G;

Назви цих методів не найвдаліші, але is_immovable() означає, що для даної симетрії «рухати» перестановку перепризначень сенсу немає, а has_bad_cycle() — що для нейтральної перестановки перепризначень немає сенсу робити перебір.

А ось, власне, сам перебір:
long long sudoku_count;

void dfs2( int x, int y )
{
while(1) // find next empty cell
{
y++;
if (y==9) { y=0; x++; }
if (x==9) // no empty cell
{
sudoku_count++;
return;
}
if (G. T[x][y]==0) break;
}

for (int a=1; a<=9; a++)
if (G. set_num( a, x, y ))
{
dfs2( x, y );
G. unset_num( a, x, y );
}
}

long long process_class( SYMMETRY s )
{
if (s==SYMMETRY::E()) return 18383222420692992L;

long long re = 0;
G. init( s );
bool imm = G. is_immovable();
bool hbc = G. has_bad_cycle();
if (imm && hbc) return re;
if (hbc) G. next_perm();

int ind = 0;
do
{
ind++;
if (ind%1000==0) fprintf( stderr, "." );
G. clear();
bool flag = true;
for (int a=1; a<=9; a++)
{
int x = (a-1)/3, y = (a-1)%3;
if (G. T[x][y]>0 && G. T[x][y]!=a) { flag = false; break; }
if (G. T[x][y]==0 && !G. set_num( a, x, y )) { flag = false; break; }
}
if (flag)
{
sudoku_count = 0;
dfs2( 0, 0 );
re += sudoku_count;
}
if (imm) break;
}
while (G. next_perm());

return re;
}

void process_all_classes()
{
long long answer = 0;
long long sum = 0;
int i = 0;
for (map< SYMMETRY, int >::iterator it = classes.begin(); it != classes.end(); it++)
{
fprintf( stderr, "class %3d", i );
long long tmp = process_class( it->first );
printf( "class %3d %6d x %17lld\n", i, it->second, tmp );
fprintf( stderr, " %6d x %17lld\n", it->second, tmp );
i++;
answer += tmp * it->second;
sum += it->second;
}
printf( "total sum %lld\n", answer );
printf( "essentialy different sudoku grids %lld\n", answer/sum );
}

У процедурі process_class() ми обробляємо кожен клас наступним чином. Якщо симетрія з даного класу нічого не змінює — то відповідь для неї ми вже знаємо з минулого частині статті. Інакше ініціалізуємо нашу структуру і натравливаем на неї евристики. Якщо пощастило — нічого не треба перебирати. Інакше все-таки доведеться перебирати. На початку перебору ми готуємо структуру і заповнюємо перший блок стандартним чином. Після цього запускаємо сам перебір пошуком в глибину dfs2().

Загальний час роботи всієї програми разом з цим кодом на моїй машині становить близько 50 хвилин. Лістинг виводу (з якого я видалив рядки, в яких кількість нерухомих точок дорівнює 0), виглядає наступним чином:
number of classes 275
class 0 1 x 18383222420692992
class 78 972 x 449445888
class 114 2916 x 155492352
class 120 x 1296 30258432
class 132 69984 x 13056
class 135 16 x 107495424
class 137 96 x 21233664
class 140 192 x 4204224
class 189 3888 x 27648
class 195 10368 x 1854
class 199 144 x 14837760
class 201 864 x 2085120
class 204 x 1728 294912
class 220 7776 x 13824
class 222 15552 x 1728
class 229 288 5184 x
class 231 1728 x 2592
class 234 3456 x 1296
class 244 93312 x 288
class 247 64 x 2508084
class 257 1152 x 6342480
class 262 15552 x 3456
class 264 31104 x 6480
class 265 2304 x 648
class 269 5184 x 323928
class 271 20736 x 288
class 274 20736 x 162
total sum 18384171550626816
essentialy different sudoku grids 5472730538
total time 3013 sec

Відповідь збігається з тим, що отримали Расселл і Джарвіс. Кількість нерухомих точок з лістингу можна порівняти з їх рассчетами тут.

Весь код нашої програми можна знайти на тут.


Випадок 4x4
Давайте подивимося на судоку порядку 2, або сітку судоку розміру 4×4, для того, щоб краще зрозуміти ідеї, які були розглянуті вище (і в попередній частині теж).

Для того, щоб порахувати кількість сіток судоку 4×4, ми почнемо — як і у випадку з випадком 9×9 — з заповнення лівого верхнього блоку стандартним способом. Це ділить кількість різних сіток судоку на 4!, оскільки у нас є рівно 4! перепризначити числа в цьому блоці.

Коли ми це зробимо, 1 і 2 опиняться на перших двох позиціях першого рядка, а 3 і 4 — на наступних двох позиціях. Для кожної з 4! розстановок, у нас є два способи вставити 3 і 4, і це впливає на загальне число різних сіток. З іншого боку, якщо ми ходимо порахувати лише кількість істотно різних сіток, порядок прямування 3 і 4 не має значення, оскільки ми можемо поміняти місцями третій і четвертий стовпці і отримати все ще коректну сітку. Так що ми можемо вважати, що 3 знаходиться в третій клітинки першого рядка, а 4 — в четвертій.

Так як 1 і 3 вже є в першому стовпці 2 і 4 повинні бути вставлені в третю і четверту клітинку у стовпці. Так як у нас два способи зробити це, наше кількість різних сіток тепер вважається відразу пачками по 4!×2×2 штук. Для підрахунку кількості істотно різних сіток, ми відзначаємо, що обмін місцями третій і четвертій рядки — це одна з симетрій сітки, так що ми можемо вважати, що 2 знаходиться в третій клітинці першого стовпця, а 4 — в четвертій. До поточного моменту наша сітка має наступний вигляд:



Оскільки у третьому рядку 2, а в третьому стовпці є 3, у клітинку (3,3) ми можемо вставити або 1, або 4.

Вправа Покажіть, що якщо в позицію (3,3) вставити 1, то це в кінцевому підсумку призведе до порушення Головного Правила.

Таким чином, в позиції (3,3) зобов'язана знаходитися число 4. У четвертому рядку, четвертому стовпці, та ще й у правому нижньому блоці — в усіх них у нас є тільки 4, тому в клітинку (4,4) ми можемо вставити будь-яке з чисел 1, 2 і 3. Це дає нам наступні три сітки, тобто для кожної з 4!×2×2, які ми нарахували раніше, є рівно 3 способи поставити наступне число в позицію (4,4) (а далі сітки заповнюються однозначним чином). Таким чином, число різних сіток судоку 4×4 одно 4!×2×2×3=288.



Вправа Заповніть до кінця всі три сітки. Після цього перевірте, що друга і третя сітки насправді еквівалентні — можна відобразити третю сітку по діагоналі (який з двох?) після чого перепризначити числа 2 і 3.

Тобто, в кінцевому підсумку, у нас залишається всього дві істотно різні сітки судоку 4×4.

Ще трохи цікавих фактів
Правильно складена головоломку судоку повинна мати єдине рішення. У загальному випадку, судоку може мати кілька рішень, але в цьому випадку логічних прийомів, які ми обговорювали в главі про підходи до вирішення, може виявитися недостатньо. Відомий приклад судоку близько 3 з 17 числами, даними спочатку, який правильно складений. Мінімальна кількість підказок для правильно складеного судоку близько 3 — невідомо (насправді, вже невідомо).

Вправа чи Можете ви навести приклад судоку, який не є правильно складеним?

Інший цікаві питання (який міг прийти вам в голову, коли ви вирішували попередню вправу): як багато різних чисел може бути використано для того, щоб головоломка була правильно складеної? Виявляється, що для судоку порядку n, для отримання єдиного рішення, необхідно використовувати мінімум n2-1 різних чисел. Якщо ми для головоломки порядку n використовуємо тільки n2-2 різних чисел, то перестановка тих чисел, яких немає в підказках, в одному з рішень дасть нам інше рішення. Зокрема, для звичайної судоку порядку 3, потрібно використовувати не менше 32-1=8 різних чисел, щоб отримати правильно складену головоломку. Інакше пазл буде мати більше одного рішення (або ні одного?).

Факт, описаний у попередньому абзаці, можна переформулювати наступним чином: якщо судоку порядку n правильно складена, то в ній має міститися щонайменше n2-1 різних чисел в самому початку. Важливо відзначити, що це не те ж саме, що якщо судоку порядку n має n2-1 різних чисел, то вона правильно складена. Згадайте, що якщо з A випливає B, то B не обов'язково слід A. Наступне вправу ілюструє цей момент спеціальним прикладом.

Вправа Наступна судоку близько 2 має 22-1=3 різних чисел. Знайдіть два різних рішення.



Для судоку 4×4, аналіз всіх (двох) випадків суттєво різних сіток доводить, що правильно складена головоломка повинна мати як мінімум чотири початкових підказки.

Нарешті, не можна не відзначити, що хоча комп'ютерні програми в мить ока вирішують судоку порядку 3, використовуючи метод перебору з поверненням, рішення судоку довільного порядку n — набагато більш складна задача. У той час як порядок судоку змінюється з n на n+1 (всього на одиницю, час, потрібний для вирішення, зростає на порядки. Доведено, що завдання вирішення судоку порядку n входить в клас NP-повних завдань. Задача називається NP-повною, якщо для неї виконуються наступні дві властивості:

  1. Рішення такої задачі можна перевірити відносно швидко, тобто за полиномиальное час.
  2. Якщо хоч одна з таких задач може бути вирішена відносно швидко, то тоді відносно швидко можна вирішити всі завдання, які задовольняють властивості (1).
Хоча і перевірити правильність розв'язання NP-повних задач — швидко і легко, поки невідомо алгоритму, який би швидко знаходив це рішення. Для алгоритмів, відомих на поточний момент, час виконання росте дуже швидко із зростанням розміру вхідних даних.

Замість висновку
І на цій сумній ноті стаття підходить до кінця, як і її переклад. Я особисто в процесі перекладу (а особливо написання коментарів) дізнався і зрозумів багато нового. Сподіваюся, ви теж.

Список літератури оригінальної статті можна переглянути тут.

Спасибі всім, хто осилив до кінця.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.