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

Привіт Хабр!

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



На жаль, оригінал даної статті написаний для дебілів дуже широкого кола читачів, в тому плані, що тема розглядається не дуже глибоко, але досить докладно. При цьому пояснюється лише загальний підхід до вирішення завдання, без технічних деталей, і, фактично, обривається на найцікавішому місці формулюванням «ну а далі вони порахували на комп'ютері». У підсумку я трохи доповнив виклад своїми коментарями: вони або відзначені курсивом, або заховані під спойлери. В них розкриваються деякі технічні моменти більш докладно. Можливо, пост разом з цими коментарями сумарно тягне на повноцінну статтю, ніж на просто переклад, але я вирішив залишити все як є (насправді, я не знайшов кнопки перекладу перекладу назад в звичайну статтю, а створювати нову публікацію лише заради цього було лінь).

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

Вперше головоломка судоку у відомому нам вигляді була опублікована в 1979 році в американському журналі Dell Magazines під назвою «Numbers in Place» за авторством Говарда Гэрнса (Howard Garns). У 1984 році судоку вперше було опубліковано в Японії в журналі Nikoli. Саме Маки Кадзи (Maki Kaji), президент компанії Nikoli (яка, до речі, спеціалізується на всяких пазлах і логічних іграх), дав головоломці назва «судоку», що в перекладі з японської означає «самотні числа». Коли гра стала популярної в Японії, на неї звернув увагу новозеландець Вейн Гулд (Wayne Gould). Вейн написав програму, яка могла генерувати сотні судоку. У 2004 році він опублікував деякі з цих пазлів у Лондонських газетах. Незабаром після цього лихоманка судоку охопила всю Англію. У 2005 році головоломка, яка стала популярною у Сполучених Штатах. Судоку почали регулярно публікуватися в безлічі газет і журналів, радуючи людей по всьому світу.

Класична версія судоку має вигляд квадратної таблиці 9×9, разом — 81 комірка. Ця таблиця розділена на 9 блоки 3×3. У деяких осередках знаходяться числа з множини {1,2,3,4,5,6,7,8,9} (ці числа не можна змінювати), інші комірки пусті. Мета гри — заповнити пусті клітинки, використовуючи тільки вищезгадані дев'ять чисел, так, щоб на кожній горизонталі, на кожній вертикалі, а також у кожному блоці кожне з чисел було б рівно один раз. Ми будемо називати ці обмеження Головним Правилом ігри.

Описані вище правила відносяться до судоку порядку 3. У загальному ж випадку, судоку порядку n — це таблиця n2×n2, розділена на n2 блоків розміру n×n кожний. І все це потрібно заповнити числами від 1 до n2 так, щоб виконувалось Головне Правило.

Наприклад, на наступній картинці можна бачити приклад судоку, а також його рішення:



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

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

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

Зазвичай цих двох правил не достатньо для повного заповнення сітки судоку. Часто потрібно більш складні методи для досягнення прогресу, а іноді потрібно перебирати варіанти і відкочуватися у разі невдалого вибору. Більш витончена стратегія полягає в тому, щоб розглянути пари або трійки клітинок у рядку, стовпці або блоці. Може виявитися, що для розглянутої пари осередків підходять тільки два числа з групи, але незрозуміло яке з них в яку з цих двох осередків помістити. Однак, з цього можна укласти, що з даної пари не можуть з'явитися на будь-яких інших місцях у розглянутій групі. Це зменшує кількість варіантів в інших порожніх клітинках і допомагає підібратися ближче до вирішення. Аналогічно, якщо трійку чисел можна помістити лише в певну трійку позицій (незрозуміло в якому порядку), то ці три числа можна виключити з розгляду для всіх інших осередків по сусідству.

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

Коли жодна з простих евристик не допомагає — потрібно спробувати вибрати порожню клітинку з найменшим числом варіантів і спробувати один з варіантів. У разі отримання протиріччя (повторювані числа в рядку, стовпці або блоці) слід скасувати всі свої дії до моменту вибору і спробувати інший варіант.

Вправа Спробуйте застосувати описані вище методи на цьому судоку:



В інтернеті можна знайти безліч інших судоку будь-якої складності і на будь-який смак.

Так скільки ж їх?
Це дуже цікаве питання. Так скільки ж різних судоку 9×9? Скількома способами можна заповнити таблицю 9×9 числами від 1 до 9 так, щоб виконувалось Головне Правило? Ми опишемо метод, з допомогою якого Бертрам Фельгенхауэр (Bertram Felgenhauer) і Фразер Джарвіс (Frazer Jarvis) вважали це кількість на початку 2006 року.

Спочатку домовимось про позначеннях. Будемо називати смугою трійку блоків, центри яких розташовані на одній горизонталі. Разом ми маємо три смуги — верхню, нижню і середню. Стеком будемо називати трійку блоків, центри яких розташовані на одній вертикалі. Стеків, як і смуг, у нас теж три — лівий, правий і середній. Клітинці на перетині i рядки та j-го стовпця будемо позначати як (i,j).

Приготування закінчені і ми готові порахувати число N — кількість різних судоку. Спершу позначимо всі блоки судоку наступним чином:



Скількома способами можна заповнити блок B1? Оскільки для блоку B1 у нас 9 чисел, одне для кажой комірки, в першу з них ми можемо записати одне з чисел одним з 9 способів. Для кожного з цих 9 способів у нас є 8 способів розмістити одне з останніх чисел рівно 8 способами. Для третьої комірки для кожного з цих 9×8 способів кількість варіантів йти далі — рівне 7. Ми, по суті, намагаємося побудувати різноманітні перестановки довжини 9 і потрібну нам кількість способів заповнити блок B1 дорівнює кількості цих перестановок— 9! = 9×8×7×6×7×4×3×2×1 = 362880. Починаючи з судоку, в якому блок B1 заповнений певним чином, ми можемо отримати судоку з будь-яким іншим заповненням блоку B1 з допомогою простого переобозначния чисел (згадаємо, що нам неважливо які числа де знаходяться — головне знати де однакові числа, а де різні). Тому, для простоти, заповнимо блок B1 числами від 1 до 9 в порядку, показаному на малюнку:



Нехай кількість судоку, в яких блок B1 заповнений саме так, як на картинці, одно N1. Загальна кількість судоку буде N1×9!, звідси N1=N/9!..

Розглянемо всі способи заповнити перший рядок у блоках B2 і B3. Оскільки 1, 2 і 3 вже присутні в блоці B1, ці числа більше не можуть бути використані в даному рядку. Тільки числа 4, 5, 6, 7, 8 і 9 з другої і третьої рядків блоку B1 можуть бути використані у першій рядку блоків B2 і B3.

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

Назвемо два з цих варіантів чистими верхніми рядками: коли числа {4,5,6}, як у другому рядку блоку B1 розташовуються разом B2, а числа {7,8,9}, як у третьому рядку блоку B1, розташовуються разом у B3 (ну і випадок, коли B2 і B3 поміняні місцями). Всі інші способи — це змішані верхні рядки, оскільки там у першій рядку B2 і B3 множини {4,5,6} і {7,8,9} змішані один з одним.

Ну так от, у нас є ці двадцять способів, і ми хочемо дізнатися, як заповнити інші комірки в першій смузі.

Вправа Подумайте трохи про те, як можна заповнити першу смугу починаючи з чистою верхнього рядка 1,2,3;{4,5,6};{7,8,9} (ми пишемо a,b,c, якщо три числа йдуть в зафіксованому порядку і {a,b,c}, якщо ці числа можуть йти в будь-якому порядку). Скільки є способів, вважаючи різні способи порядку в B2 і B3? Вірно, що цих способів стільки ж, скільки і для іншої чистої рядка 1,2,3;{7,8,9};{4,5,6}?

Пам'ятайте, ми не міняємо порядок в блоці B1, оскільки ми вже враховуємо колчество сіток, які виходять шляхом перемішування девяки чисел B1.

Виявляється, для чистої верхнього рядка 1,2,3;{4,5,6};{7,8,9} — рівне (3!)6 способів, оскільки нам обов'язково потрібно помістити {7,8,9};{1,2,3} на другий рядок у блоках B2 і B3, а {1,2,3};{4,5,6} — на третій рядок. Після цього ми можемо довільним чином змінювати місцями числа цих шести трійках в B2 і B3 для того, щоб отримати всі конфігурації. Для другої чистої верхнього рядка відповідь той же, оскільки все, що ми міняється місцями — це блоки B2 і B3.

Для випадку мішаних верхніх рядків всі неммого складніше. Давайте розглянемо верхню рядок 1,2,3;{4,6,8};{5,7,9}. Далі першу смугу можна заповнити так, як показано на зображенні нижче, де a, b і c — це числа 1, 2, 3 в будь-якому порядку.



Як тільки число a вибрано, b і c — це два числа в будь-якому порядку, оскільки вони знаходяться в одних і тих же рядках. Для a три способи вибору, а потім ми можемо просто перемішати числа шести трійках в B2 і B3 в будь-якому порядку — і завжди буде виходити відповідна перша смуга. Отже, кількість конфігурацій — 3x(3!)6. Нескладно показати, що в останніх сімнадцяти способи ми отримаємо те ж саме число.

Тепер ми можемо порахувати загальну кількість різних верхніх смуг для фіксованого блоку B1: 2х(3!)6+18x3x(3!)6=2612736. Перша частина суми — це кількість смуг для чистих верхніх смуг, а друга — для змішаних.

Замість того, щоб порахувати кількість разничных повністю заповнених сіток для кожного з цих 2612736 варіантів, Фельгенхауэр і Джарвіс спочатку визначили у яких із цих верхніх смуг одне і те ж кількість варіантів повного заповнення. Цей аналіз скорочує кількість смуг, які нам потрібно буде розглянути для подальших розрахунків.

Є кілька операцій, які залишають кількість повністю заповнених сіток незмінним: перепризначення чисел, перестановка будь-яких блоків у першій смузі, перемішування стовпців в будь-якому блоці, зміна порядку трьох рядків у смузі. Як тільки якісь з операцій змінюють порядок чисел B1 — ми просто переназначаем числа так, щоб привести блок B1 до стандартного вигляду.

Коли ми міняємо місцями блоки B1, B2 і B3 — кількість заповнень сіток зберігається, оскільки ми починаємо з коректної сітки судоку, і єдиний спосіб зберегти коректність надалі — це поменяить місцями B4, B5, B6 і B7, B8, B9 так, як ми поміняли B1, B2, B3. У підсумку всі стеки залишаться тими ж самими. Іншими словами, кожне коректне заповнення всієї сітки для однієї верхньої смуги дає рівно один коректне заповнення сітки для іншої верхньої смуги, отриманої перемішуванням блоків B1, B2, B3.

Вправа Переконайтеся самі, що якщо поміняти місцями блоки B2 і B3 в такій сітці, то єдиний спосіб зберегти сітку коректної — це поміняти місцями B5 та B6, а також B8 і B9. Стеки залишаються ті ж самі, але змінюються їх розташування.



Вправа Нехай у вас є коректно заповнена сітка судоку і ви міняєте місцями деякі стовпці в одному з блоків B1, B2 або B3. Що потрібно зробити з іншими стовпцями, щоб сітка судоку залишилася коректної? Наприклад, якщо ви поміняли місцями перший і другий стовпці в блоці B2, як би ви виправили частину сітки так, щоб вона задовольняла Головному Правилу?

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

Це спостереження дозволяє нам зменшити кількість перших смуг, які нам потрібно розглянути. Згідно Фельгенхауэру і Джарвіс, ми перемішуємо стовпці в блоках B2 і B3 таким чином, що значення в самій верхній рядку йдуть у зростаючому порядку. Після цього ми можливо міняємо місцями блоки B2 і B3 так, щоб перше число в блоці B2 (ліве верхнє) було менше, ніж перше число в блоці B3. Ця операція називається лексикографічною редукцією. Оскільки для кожного з двох блоків у нас рівно 6 різних перестановок і всього 2 способи упорядкувати блоки один відносно одного, лексикографічна редукція говорить нам, що для будь-першої смуги можна побудувати клас з 62×2=72 перших смуг з одним і тим же кількістю повних заповнень сіток (і для всіх елементів з кожного класу це побудова призводитиме до цього ж класу). Таким чином, нам тепер потрібно розглянути тільки 2612736/72=36288 перших смуг.

КоментарДумаю, тут саме час почати писати код для того, щоб зробити статтю трохи більше хардкорного. Ми збираємося перевірити, що лексикографічно редукованих верхніх смуг, в яких блок B1 стандартний — рівне 36288 штук.

Для початку опишемо структуру для нашої смуги (я, як завжди, пишу на C++):
struct BAND
{
int m[3][3][3]; // 3 blocks of 3x3 grids

BAND()
{
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
for (int k=0; k<3; k++)
m[i][j][k] = 0;
}

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

bool is_valid( bool with_zeros )
{
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
for (int k=0; k<3; k++)
{
if (!(0 < =m[i][j][k] && m[i][j][k]<=9)) return false;
if (!with_zeros && m[i][j][k]==0) return false;
}

bool F[10];
for (int i=0; i < 3; i++) // check blocks
{
memset( F, 0, sizeof( F ) );
for (int j=0; j < 3; j++)
for (int k=0; k<3; k++)
{
if (F[m[i][j][k]]) return false;
if (m[i][j][k]>0) F[m[i][j][k]] = true;
}
}
for (int i=0; i < 3; i++) // check rows
{
memset( F, 0, sizeof( F ) );
for (int j=0; j < 3; j++)
for (int k=0; k<3; k++)
{
if (F[m[j][i][k]]) return false;
if (m[j][i][k]>0) F[m[j][i][k]] = true;
}
}
return true;
}
};

У коді пояснень заслуговує хіба що метод is_valid(): він перевіряє, що Головне Правило для смуги виконується. Якщо аргумент with_zeros дорівнює true, то метод не приймає до уваги нулі (а нулями ми будемо позначати осередку частково заповнених смуг, які поки ще не призначено ні одна цифра).

Код для генерації всіх нас цікавлять смуг виглядає наступним чином:
void gen_bands( BAND band, int block, int row, int col, vector< BAND > & res )
{
col++; // move to the next empty cell
if (col==3) { col=0; row++; }
if (row==3) { row=1; block++; }
if (block==3) // no next empty cell
{
res.push_back( band );
return;
}

for (int a=1; a<=9; a++)
{
band.m[block][row][col] = a;
if (band.is_valid( true ))
gen_bands( band, block, row, col, res );
}
}

vector< BAND > gen_all_bands()
{
BAND b0;
int t=1;
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
b0.m[0][i][j] = t++;
// b0 has standard block B1; B2 and B3 are empty

vector< BAND > starting_bands;
for (int a=4; a<=4; a++)
for (int b=a+1; b<=9; b++)
for (int c=b+1; c<=9; c++)
{
BAND b1 = b0;
b1.m[1][0][0] = a;
b1.m[1][0][1] = b;
b1.m[1][0][2] = c;
int ind = 0;
for (int d=4; d<=9; d++)
if (d!=a && d!=b && d!=c)
b1.m[2][0][ind++] = d;
//b1.print();
starting_bands.push_back( b1 );
}
// we filled the first row by all possible ways
printf( "bands filled with the first row %d\n", (int)starting_bands.size() ); // 10 bands total

vector< BAND > reduced_bands;
for (int i=0; i<(int)starting_bands.size(); i++)
gen_bands( starting_bands[i], 0, 2, 2, reduced_bands );
printf( "lexicographically reduced bands %d\n", (int)reduced_bands.size() ); // 36288 bands total

return reduced_bands;
}

Спочатку ми готуємо starting_bands — смуги, в яких заповнений блок B1 і перші рядки блоків B2 і B3. Їх всього 10 штук, оскільки для підтримки лексикографічного порядку ми не враховуємо варіанти, коли блок B2 «більше» блоку B3. Після цього ми простеньким перебором знаходимо всі шукані смуги. Розрахунки, наведені вище по тексту в коді не використовуються — вони більше для «голови», ніж для машини. Головне що числа в підсумку зійшлися. А згенеровані смуги потім ми ще будемо використовувати в наступному спойлері.

Для кожного з цих варіантів розглянемо всілякі перестановки трьох верхніх блоків: їх рівно 6. А для кожного з цих варіантів є 63 перестановок стовпців всередині всіх блоків. Після того, як ми все перемішали, ви переназначаем числа так, щоб у блоці B1 вони всі йшли в стандартному порядку. Ми також можемо довільно перемішати три верхні рядки, після чого знову перепризначити числа, щоб блок B1 став стандартним. Після кожної з цих операцій кількість заповнення всієї сітки для даної першої смуги залишиться незмінним. Фельгенхауэр і Джарвіс за допомогою комп'ютерної програми визначили, що ці операції скорочують кількість перших смуг, які має сенс розглядати, з 36288 до всього лише 416.

Вправа Розгляньте певну першу смугу. Зробіть над нею деякі операції, які зберігають кількість заповнень всієї сітки судоку. Можете почати з наступного: поміняйте місцями першу і другу рядка. Після цього переназначьте числа в блоці B1, щоб привести його до стандартної формі. Виконайте лексикографічну редукцію.

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

КоментарПочинаючи з цього моменту починаються деякі неочевидності — автори оригінал пропонують повірити їм наслово. Але ми не такі — ми будемо писати код для того, щоб пересвідчитися особисто. А саме: зараз ми будемо перевіряти той факт, що виконуючи описані вище операції, ми в результаті отримаємо рівно 416 варіантів.

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

Спершу внесемо зміни у структуру BAND:
struct BAND
{
/* old code */

void normalize() // turn into standard form
{
// relabeling
int relabel[10];
int t = 1;
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
relabel[m[0][i][j]] = t++;
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
for (int k=0; k<3; k++)
m[i][j][k] = relabel[m[i][j][k]];

// lexicographic reduction
for (int i=1; i < 3; i++)
{
if (m[i][0][0] > m[i][0][1])
for (int j=0; j < 3; j++)
swap( m[i][j][0], m[i][j][1] );
if (m[i][0][1] > m[i][0][2])
for (int j=0; j < 3; j++)
swap( m[i][j][1], m[i][j][2] );
if (m[i][0][0] > m[i][0][1])
for (int j=0; j < 3; j++)
swap( m[i][j][0], m[i][j][1] );
}

// swap B2 and B3
if (m[1][0][0] > m[2][0][0])
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
swap( m[1][i][j], m[2][i][j] );
}

BAND get_copy()
{
BAND re;
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
for (int k=0; k<3; k++)
re.m[i][j][k] = m[i][j][k];
return re;
}

BAND swap_blocks( int x, int y ) // swap blocks x and y
{
BAND re = get_copy();
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
swap( re.m[x][i][j], re.m[y][i][j] );
re.normalize();
return re;
}

BAND swap_rows( int x, int y ) // swap rows x and y
{
BAND re = get_copy();
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
swap( re.m[i][x][j], re.m[i][y][j] );
re.normalize();
return re;
}

BAND swap_columns( int b, int x, int y ) // swap columns x and y in block b
{
BAND re = get_copy();
for (int i=0; i < 3; i++)
swap( re.m[b][i][x], re.m[b][i][y] );
re.normalize();
return re;
}
};

Тепер ми можемо нашу смугу лексикографічно редукувати (метод normalize()), а також робити все 3 операції, описані вище. При застосуванні операції створюється копія об'єкта, потім до копії застосовується операція, потім результат нормалізується (щоб не виходити за межі редукованих 36288 смуг).

Тепер ми можемо порахувати кількість компонент зв'язності за допомогою стандартного обхід в глибину. При цьому граф явно не будується.
bool operator< ( const BAND & A, const BAND & B )
{
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
for (int k=0; k<3; k++)
if (A. m[i][j][k] != B. m[i][j][k])
return A. m[i][j][k] < B. m[i][j][k];
return false;
}

bool operator== ( const BAND & A, const BAND & B )
{
for (int i=0; i < 3; i++)
for (int j=0; j < 3; j++)
for (int k=0; k<3; k++)
if (A. m[i][j][k] != B. m[i][j][k])
return false;
return true;
}

set< BAND > used_bands;
int comp_size;

void dfs( BAND b )
{
if (used_bands.find( b ) != used_bands.end()) return;
comp_size++;
used_bands.insert( b );

for (int i=0; i < 3; i++)
for (int j=i+1; j < 3; j++)
{
dfs( b.swap_blocks( i, j ) );
dfs( b.swap_rows( i, j ) );
for (int k=0; k<3; k++)
dfs( b.swap_columns( k, i, j ) );
}
}

void solution()
{
vector< BAND > bands = gen_all_bands();

vector< int > comp_sizes;
vector< BAND > ident_bands;
for (int i=0; i<(int)bands.size(); i++)
if (used_bands.find( bands[i] ) == used_bands.end())
{
comp_size = 0;
dfs( bands[i] );
comp_sizes.push_back( comp_size );
ident_bands.push_back( bands[i] );
}

printf( "number of connected components %d\n", (int)comp_sizes.size() ); // 416 components
for (int i=0; i<(int)comp_sizes.size(); i++)
printf( "%d ", comp_sizes[i] );
}

Оператори порівняння потрібні для того, щоб їх міг використовувати set. У підсумку програма дійсно знаходить рівно 416 компонент зв'язності. У comp_sizes складаються розміри цих компонент, а в ident_bands — одна з вершин з кожної компоненти (смуга — представник класу). Слід зазначити, що отримуються компоненти не завжди мають однаковий розмір. Наприклад, програма виводить наступні розміри:

1 27 18 54 6 9 54 108 9 54 108 54 54 108 54 54 54 18 6 108 54 54 6 18 6 54 18 54 18 54 2 54 108 108 108 54 108 108 108 108 54 108 108 108 54 108 108 54 108 54 108 54 108 108 108 54 108 108 108 54 108 108 108 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 108 108 108 108 108 108 54 108 108 108 108 54 108 108 108 18 108 108 54 108 108 108 54 54 108 108 108 54 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 54 54 18 54 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 108 108 108 54 108 108 54 108 108 108 108 108 108 108 108 108 36 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 54 108 108 108 108 108 108 108 54 108 108 108 54 108 108 108 108 54 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 108 54 108 108 54 108 108 108 108 108 54 108 108 108 108 108 108 54 54 54 54 54 54 6 18 54 18 108 54 54 108 54 54 108 54 54 108 108 108 108 54 108 108 108 108 108 54 108 108 108 108 108 108 108 54 54 108 108 108 108 108 54 108 54 108 108 54 54 108 108 108 108 108 108 54 18 18 54 54 108 54 54 108 108 54 108 108 54 108 108 108 108 108 54 108 54 18 54 108 108 54 54 108 108 54 54 108 108 108 54 54 108 108 108 108 108 108 108 54 36 108 108 108 108 108 54 108 108 108 108 108 54 108 108 54 54 108 54 108 108 108 54 54 108 108 108 54 18 108 54 54 54 108 54 18 18 54 54 54 108 18 54 54 54 54 3 27 9 9 
 


Ну і тепер, по суті, можна порахувати кількість підсумкових заповнень для кожного представника, помножити на кількість вершин у відповідній компоненті і в кінці все скласти. Але з цим поки що не будемо поспішати.




Існує ще кілька операцій, які скорочують кількість сіток для розгляду. Якщо у нас є пара чисел {a,b} така, що a та b знаходяться в одному стовпці, причому a — на i-й рядку, а b — на j-ой, і, до всього іншого, є така ж пара в іншому стовпці, причому для цього стовпця a вже знаходиться на j-му рядку, а b — на i-ої (тобто ці чотири числа знаходяться в кутах деякого прямокутника, і протилежні числа дорівнюють), то ми можемо поміняти місцями числа в обох парах і отримати нову коректну смугу з тією ж кількістю кінцевих сіток. Наприклад, в судоку, наведеному трохи вище, числа 8 і 9 у шостому і дев'ятому стовпцях формують таку конфігурацію. Розглянувши всі можливі випадки, Фельгенхауэр і Джарвіс скоротили необхідну для розгляду число перших смуг з 416 до 174.

Але і це ще не все. Вони розглянули інші конфігурації однакових множин (з трьох і більше чисел), розташовані один навпроти одного в двох різних стовпцях або рядках, які можна поміняти місцями і відповідь від цього не зміниться. Це скорочує кількість варіантів до 71, а якщо додатково розглянути ці варіанти і застосувати більш складні симетрії — кількість смуг для розгляду можна скоротити до 44. І для кожної з цих 44 смуг всі інші смуги у відповідному класі мають таке ж кількість повних заповнень всієї сітки.

КоментарДавайте доповнимо нашу програму новими операціями для того, щоб отримати поліпшення до 174 і до 71 смуги. До 44 смуг ми покращувати не будемо — там все зовсім складно, та й виразної інформації про це дуже мало. Фельгенхауэр і Джарвіс у своїй статті покращують тільки до 71, а число 44 вони призводять вже в кінці після всіх обчислень (втім, вони також пишуть, що там є відповідні перетворення, щоб отримати шукані 44 смуги — про це в кінці даного спойлера).

Отже, завайте додамо операцію свапания двох пар чисел, які розташовуються в кутах одного прямокутника. До вже написаного коду додати це дуже просто:
struct BAND
{
/* old code */

BAND swap_cross( int b1, int b2, int r1, int r2, int c1, int c2 )
{
BAND re = get_copy();
// note: b1 must be together with b2 c1 and must be together with c2
if (re.m[b1][r1][c1] == re.m[b2][r2][c2] && re.m[b1][r2][c1] == re.m[b2][r1][c2])
{
swap( re.m[b1][r1][c1], re.m[b2][r1][c2] );
swap( re.m[b1][r2][c1], re.m[b2][r2][c2] );
}
re.normalize();
return re;
}
};

void dfs( BAND b )
{
/* old code */

for (int b1=0; b1<3; b1++)
for (int b2=b1+1; b2<3; b2++)
for (int r1=0; r1<3; r1++)
for (int r2=r1+1; r2<3; r2++)
for (int c1=0; c1<3; c1++)
for (int c2=0; c2<3; c2++)
dfs( b.swap_cross( b1, b2, r1, r2, c1, c2 ) );
}

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

Якщо запустити оновлений код — ми отримаємо, як і очікувалося, рівне 174 смуги.

Додамо ще операцій:
struct BAND
{
/* old code */

BAND swap_3x2( int b1, int b2, int c1, int c2 )
{
BAND re = get_copy();
// note: b1 must be together with b2 c1 and must be together with c2
if (( re.m[b1][0][c1] == re.m[b2][1][c2] &&
re.m[b1][1][c1] == re.m[b2][2][c2] &&
re.m[b1][2][c1] == re.m[b2][0][c2]) ||
( re.m[b1][0][c1] == re.m[b2][2][c2] &&
re.m[b1][1][c1] == re.m[b2][0][c2] &&
re.m[b1][2][c1] == re.m[b2][1][c2]))
{
swap( re.m[b1][0][c1], re.m[b2][0][c2] );
swap( re.m[b1][1][c1], re.m[b2][1][2] );
swap( re.m[b1][2][c1], re.m[b2][2][c2] );
}
re.normalize();
return re;
}

BAND swap_mask( int r1, int r2, int mask )
{
BAND re = get_copy();
int num1=0, num2=0;
for (int i=0; i < 3; i++) // block
for (int j=0; j < 3; j++) // col
if ((mask>>(i*3+j))&1)
{
num1 += (1<<re.m[i][r1][j]);
num2 += (1<<re.m[i][r2][j]);
}
if (num1 == num2)
for (int i=0; i < 3; i++) // block
for (int j=0; j < 3; j++) // col
if ((mask>>(i*3+j))&1)
swap( re.m[i][r1][j], re.m[i][r2][j] );
re.normalize();
return re;
}
};

void dfs( BAND b )
{
/* old code */

for (int b1=0; b1<3; b1++)
for (int b2=b1+1; b2<3; b2++)
for (int c1=0; c1<3; c1++)
for (int c2=0; c2<3; c2++)
dfs( b.swap_3x2( b1, b2, c1, c2 ) );

for (int r1=0; r1<3; r1++)
for (int r2=r1+1; r2<3; r2++)
for (int mask=1; mask<(1<<9); mask++)
dfs( b.swap_mask( r1, r2, mask ) );
}

Перша з операцій swap_3x2() — це випадок, коли ми шукаємо однакові підмножини в двох стовпцях. Справа в тому, що підмножина розміру 1 не буває (інакше порушується Головне Правило), підмножина розміру 2 вже опрацьовується процедурою swap_cross(), а всього рядків у нас 3. Значить, нам потрібно перевіряти лише один варіант — всі три числа в двох стовпцях. Для них існують рівно два варіанти відповідності:



Якщо все співпало — ми просто змінюємо місцями стовпці. Інакше — залишаємо смугу незмінною.

Для другої операції swap_mask() ми перебираємо всілякі підмножини стовпців і дивимося для двох рядків — чи однакові виходять безлічі чисел для цих підмножин стовпців. Приклади відповідних варіантів:




При збігу ми міняємо місцями знайдені підмножини (свапаем пару в кожному стовпці). При неспівпадінні — нічого не робимо.

Слід зазначити, що розглянута раніше операція swap_cross() — це приватний випадок swap_mask(). Тому swap_cross() можна взагалі викинути непотріб.

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

Розміри компонент зв'язності виходять наступні:
4 108 72 216 24 216 216 2592 216 216 1296 1404 540 108 72 510 702 270 2214 6 504 6 1350 666 702 18 756 20 2268 1134 2592 972 270 864 864 972 2052 486 270 1620 540 432 144 432 864 324 540 270 270 234 6 18 540 288 216 54 108 108 288 54 378 108 108 54 108 54 108 36 108 54 54 
 

Що ж до операцій, які скорочують число варіантів до 44, то вони виглядають так:



Можете спробувати описати їх більш формально і реалізувати в коді.

Нехай C — одна з 44 смуг. Тоді кількість способів, якими C можна доповнити до повної сітки судоку, позначимо на nC. Нам також знадобиться число mC — загальна кількість смуг, для яких кількість кінцевих заповнень таке ж, як і у C. Коли загальна кількість різних судоку буде дорівнює N=ΣCmCnC, тобто сума mCnC по всім 44 смугах.

Фельгенхауэр і Джарвіс написали комп'ютерну програму для виконання підсумкових розрахунків. Вони вирахували число N1 (кількість коректних заповнень, в яких B1 в стандартній формі) для кожної з 44 смуг. Потім вони помножили це число за 9!, щоб отримати відповідь. Вони виявили, що кількість всіляких коректних сіток судоку 9 на 9 дорівнює N=6670903752021072936960, що приблизно дорівнює 6.671×1021.

КоментарДавайте і ми допишемо нашу програму для розрахунків. Почнемо зі структури GRID — сітки судоку, в яку можна вписувати числа і для кожної порожньої клітинки дізнаватися чи можна в неї записати будь-яке число чи ні.
struct GRID
{
int T[9][9];
bool R[9][10], C[9][10], B[9][10];

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

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

bool can_set( int num, int x, int y )
{
return !R[x][num] && !C[y][num] && !B[(x/3)*3+(y/3)][num];
}

void set_num( int num, int x, int y )
{
T[x][y] = num;
R[x][num] = true;
C[y][num] = true;
B[(x/3)*3+(y/3)][num] = true;
}

void unset_num( int num, int x, int y )
{
T[x][y] = 0;
R[x][num] = false;
C[y][num] = false;
B[(x/3)*3+(y/3)][num] = false;
}
} G;

Масиви прапорів R, C і B зберігають інформацію про те, які вже відзначені у відповідних рядках, стовпцях і блоках. Це дозволяє потім швидко визначити, чи можна поставити у яку-небудь клітинку яке-небудь число чи ні.

Наступна процедура для кожної смуги BAND будує початкову сітку для перебору GRID і запускає перебір:
long long process_band( BAND band )
{
int nums[] = { 2, 3, 5, 6, 8, 9 };
long long res = 0;

for (int i=1; i < 6; i++)
for (int j=i+1; j<6; j++)
{
G. clear();

for (int a=0; a<3; a++)
for (int b=0; b<3; b++)
for (int c=0; c<3; c++)
G. set_num( band.m[a][b][c], b, a*3+c );

G. set_num( nums[0], 3, 0 );
G. set_num( nums[i], 4, 0 );
G. set_num( nums[j], 5, 0 );
int t = 6;
for (int k=1; k<6; k++)
if (k!=i && k!=j)
G. set_num( nums[k], t++, 0 );
// starting grid is complete
//G. print();

grids_count = 0;
dfs2( 8, 0 );
res += grids_count;
fprintf( stderr, "." );
}

return res;
}

Насправді, дана процедура в самому початку заповнює перший стовпець сітки, та не всіма способами, а тільки лексикографічно редукованими — це скорочує подальший перебір рівно 72 рази (головне потім не забути домножить відповідь на 72). Разом кожен виклик процедури process_band() запускає dfs2() рівно 10 разів.

Сам же перебір виглядає наступним чином:
int grids_count;

void dfs2( int x, int y )
{
x++; // find next empty cell
if (x==9) { x=3; y++; }
if (y==9) // no empty cells
{
grids_count++;
return;
}

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

Перебір абсолютно нехитрий. Ми перебираємо всі залишилися незаповнені клітини в наступному порядку: спочатку йдемо зверху вниз з другого стовпця (в блоках B4 і B7), потім йдемо зверху вниз по третьому стовпцю і так далі.

Один запуск dfs2() на моїй машині працює близько 30 секунд, тобто на обробку однієї смуги потрібно близько 5 хвилин. Реалізацію, звичайно ж, можна трохи прискорити, ви можете спробувати зробити це самостійно. Програма Фельгенхауэра і Джарвіса для однієї смуги працює близько 2 хвилин (як вони пишуть у своїй статті), тобто всього в 2,5 рази швидше нашій реалізації. Повна обробка всіх 71 смуг (для нашої програми) займає 6 годин.

В результаті роботи програма виводить наступне:
bands filled with the first row 10
lexicographically reduced bands 36288
number of connected components 71
0/71 4 x 108374976
1/71 108 x 102543168
2/71 72 x 100231616
3/71 216 x 99083712
4/71 24 x 97282720
5/71 216 x 102047904
6/71 216 x 98875264
7/71 2592 x 98733568
8/71 216 x 98875264
9/71 216 x 99525184
10/71 1296 x 98369440
11/71 1404 x 97287008
12/71 540 x 98128064
13/71 108 x 98128064
14/71 72 x 97685328
15/71 510 x 98950072
16/71 702 x 98153104
17/71 270 x 97961464
18/71 2214 x 97961464
19/71 6 x 98950072
20/71 504 x 97685328
21/71 6 x 99258880
22/71 1350 x 97477096
23/71 666 x 97549160
24/71 702 x 97477096
25/71 18 x 97549160
26/71 756 x 96702240
27/71 20 x 94888576
28/71 2268 x 97116296
29/71 1134 x 98371664
30/71 2592 x 97539392
31/71 972 x 97910032
32/71 270 x 98493856
33/71 864 x 98119872
34/71 864 x 98733184
35/71 972 x 97116296
36/71 2052 x 96482296
37/71 486 x 97346960
38/71 270 x 97346960
39/71 1620 x 97416016
40/71 540 x 97455648
41/71 432 x 98784768
42/71 144 x 101131392
43/71 432 x 97992064
44/71 864 x 97756224
45/71 324 x 96380896
46/71 540 x 97910032
47/71 270 x 97416016
48/71 270 x 97714592
49/71 234 x 96100688
50/71 6 x 99258880
51/71 18 x 96100688
52/71 540 x 96482296
53/71 288 x 96807424
54/71 216 x 97372400
55/71 54 x 97714592
56/71 108 x 97372400
57/71 108 x 95596592
58/71 288 x 96631520
59/71 54 x 95596592
60/71 378 x 95596592
61/71 108 x 96482296
62/71 108 x 96482296
63/71 54 x 98371664
64/71 108 x 97455648
65/71 54 x 97416016
66/71 108 x 97287008
67/71 36 x 97372400
68/71 108 x 98048704
69/71 54 x 98493856
70/71 54 x 98153104
total number of sudoku 3546146300288*9!*72*72
total time 21213 sec

Для отримання фінального результату потрібно скористатися калькулятором (довгу арифметику писати не хотілося), і… все збігається! Можете звірити числа з тими, що вийшли у Фельгенхауэра і Джарвіса тут.

Повний код нашої програми (щоб не збирати шматками з спойлерів) перебуває тут.

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

0 коментарів

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