Пилипчук О.П., вчитель інформатики Гаврилівської ЗОШ Теофіпольського району Хмельницької області

Розв'язуємо судоку

Об'єктноорієнтоване програмування мовою C++

 Популярна головоломка "Судоку", незважаючи на простий вигляд, дарує своїм фанатам багато годин інтелектуальної праці. Суть головоломки така. У деяких клітинках квадратної таблиці з 9 рядків та 9 стовпців написані цифри:


Потрібно заповнити порожні клітинки цифрами так, щоб кожен рядок, кожен стовпець і кожен з виділених на малюнку квадратів розміром 3*3 містили всі цифри від 1 до 9.

Ідея написати програму для розв'язування судоку виникла після того, як на відкритій заочній олімпіаді з програмування серед учнів навчальних закладів Хмельницької області 2008 року була запропонована така задача (автор - програміст Попик А.В.):

Задача t2z3. "Судоку"

Поле для гри в судоку має розмір 9х9 клітинок і умовно розбите на 9 квадратів розміром 3х3. Кожна клітинка є або пустою, або містить число від 1 до 9.

Приклад:

3 8 9 | 7 . . | 2 . .
6 7 2 | . 5 . | . 1 .
. 1 4 | 6 . 9 | . . 3
- - - - - - - - - - -
2 3 . | 5 . . | 8 7 1
8 5 . | . 3 7 | . 4 9
4 9 7 | 8 1 . | 3 . 5
- - - - - - - - - - -
. 6 5 | 4 8 2 | 1 3 .
1 . 3 | . 7 . | 4 6 .
7 4 . | 1 . 3 | 5 9 .

Вам необхідно розставити в порожні клітинки числа від 1 до 9 так, щоб:

1. в кожному рядку числа не повторювались
2. в кожному стовпчику числа не повторювались
3. в кожному з 9-ти умовних квадратів числа не повторювались.
   

Для вищенаведеного прикладу відповідь така:

3 8 9 | 7 4 1 | 2 5 6
6 7 2 | 3 5 8 | 9 1 4
5 1 4 | 6 2 9 | 7 8 3
- - - - - - - - - - -
2 3 6 | 5 9 4 | 8 7 1
8 5 1 | 2 3 7 | 6 4 9
4 9 7 | 8 1 6 | 3 2 5
- - - - - - - - - - -
9 6 5 | 4 8 2 | 1 3 7
1 2 3 | 9 7 5 | 4 6 8
7 4 8 | 1 6 3 | 5 9 2

Вхідні дані:

У стандартному вхідному потоці записані 9 рядків по 9 чисел.(числа розділені пропусками). Пуста клітинка позначена числом 0. Нулів (пустих клітинок) буде не більше ніж 29.

Вихідні дані:

У стандартний вихідний потік запишіть відповідь до заданого судоку - 9 рядків по 9 чисел в кожному (розділені пропусками!!!)

Приклад вхідних даних:

3 8 9 7 0 0 2 0 0
6 7 2 0 5 0 0 1 0
0 1 4 6 0 9 0 0 3
2 3 0 5 0 0 8 7 1
8 5 0 0 3 7 0 4 9
4 9 7 8 1 0 3 0 5
0 6 5 4 8 2 1 3 0
1 0 3 0 7 0 4 6 0
7 4 0 1 0 3 5 9 0

Приклад вихідних даних:

3 8 9 7 4 1 2 5 6
6 7 2 3 5 8 9 1 4
5 1 4 6 2 9 7 8 3
2 3 6 5 9 4 8 7 1
8 5 1 2 3 7 6 4 9
4 9 7 8 1 6 3 2 5
9 6 5 4 8 2 1 3 7
1 2 3 9 7 5 4 6 8
7 4 8 1 6 3 5 9 2

Ідея

Задачі "розв'язати головоломку" і "скласти програму для розв'язування головоломки" суттєво відрізняються, тому можна успішно скласти програму не маючи досвіду розв'язування судоку. Оберемо найпростіший спосіб - перебір можливих варіантів розстановки цифр. Якщо в процесі перебору буде знайдено розв'язок - просто виведемо його.

Нехай при зчитуванні даних з файлу в клітинку на перетині рядка R і стовпця C записана цифра N. При цьому слід заблокувати інші клітинки рядка R, стовпця C і квадратика 3*3, який містить цю клітинку, так, щоб в них неможливо було записати число N.

Загальний алгоритм такий:

1. перебираючи цифри рядок за рядком, знайти нуль;
2. якщо нуля знайти не вдалося - задача розв'язана :). Кінець.
3. для кожної з цифр, від яких знайдена клітинка не заблокована:
• записати в клітинку цю цифру;
• заблокувати інші клітинки рядка R, стовпця C і квадратика 3*3, який містить цю клітинку, так, щоб в них неможливо було записати таку цифру;
• перейти до пункту 1.

Як бачимо,  повторний виклик алгоритму (перехід до пункту 1)  виникає до повного завершення циклу в пункті 3, тобто, алгоритм є рекурсивним.

Розробка проекту

Примітка. Якщо з подальшого тексту вилучити пояснення - залишиться працездатна програма.

1. Умова задачі передбачає файлове введення/виведення, тому слід підключити відповідну бібліотеку:

#include <fstream>
using namespace std;

2. Поставимо додаткове завдання: програма має бути об'єктноорієнтованою. Розпочати варто з побудови об'єктної моделі. Задача досить наочна - у ній фігурують об'єкти двох класів: клітинки та ігрове поле.

class cell {

3. Клас cell моделює клітинку таблиці. Розробляючи його слід добре продумати, якою має бути "поведінка" клітинки в процесі роботи програми. Повинна бути можливість заблокувати клітинку від встановлення певних цифр, тому надамо клітинці масив з 9 цілих чисел (індекси - від 0 до 9). Якщо елемент цього масиву з індексом N відмінний від нуля - у клітинку не можна записувати цифру N+1:

     int blocks [9];

Зовнішній доступ до масиву blocks заборонений, а решту полів і методів опишемо в секції public:

     public:

4. Клітинка в кожен момент містить якусь цифру (можливо, нуль). Для її зберігання введемо поле V:

     int V;

Заносити цифру в клітинку будемо звичайним присвоюванням.

5. При створенні клітинки слід зробити деякі початкові налаштування: занести цифру нуль, позначити клітинку як вільну і зняти блокування для всіх цифр. Опишемо ці налаштування у методі-конструкторі:

     cell () {V=0; for (int i=0; i<9; i++) blocks[i]=0;}

6. В процесі роботи потрібно буде перевіряти, чи можна в цю клітинку вписати цифру v. Повідомлятиме про це метод Can:

bool Can (int v) {return !V && !blocks[v-1];}

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

7. Створимо метод BlockTo, який дозволить заблокувати клітинку від встановлення цифри v:

     void BlockTo (int v) {blocks[v-1]++;}

і метод UnBlockTo, який дозволить знімати таке блокування.

     void UnBlockTo (int v) {blocks[v-1]--;}

Зверніть увагу, що при блокуванні відповідний елемент масиву blocks не просто отримує відмінне від нуля значення, а збільшується на одиницю, а при розблокуванні - зменшується. Це дозволяє говорити про "глибину" блокування і спростить побудову рекурсивної процедури розв'язування задачі.

8. Вписавши в клітинку цифру, прочитану з вхідного файлу, потрібно заблокувати її від подальших змін. Це реалізує метод SetHardTo:

     void SetHardTo (int v)
{V=v; for (int i=0; i<9; i++) blocks[i]++;}
};

Це всі властивості, які повинна мати клітинка.

9. Для роботи з ігровим полем створюємо клас field:

class field {

Він містить прямокутний масив клітинок, тобто, об'єктів типу cell:

     cell M[9][9];

і файлові потоки f1 та f2 для введення та виведення даних відповідно, які при створенні об'єкту типу field будуть зв'язані з конкретними файлами:

     ifstream f1;
ofstream f2;

10. Перш за все створимо умови для зчитування початкових даних. Записуючи цифру K у клітинку з координатами r i c, потрібно заблокувати інші клітинки рядка r, стовпчика c і відповідного квадрата 3*3 від встановлення такої ж цифри. Сама ж клітинка має бути повністю захищена від змін (метод SetHardTo об'єкту типу cell):

     void FillHard (int r, int c, int K)
{  M[r][c].SetHardTo(K);
for (int R=0; R<9; R++) if (R!=r) M[R][c].BlockTo(K); //блокуємо стовпець
for (int C=0; C<9; C++) if (C!=c) M[r][C].BlockTo(K); // блокуємо рядок
int dr=r/3*3, dc=c/3*3;
for (int R=0; R<3; R++) // блокуємо квадратик
for (int C=0; C<3; C++)
if ((R!=r)&&(C!=c)) {M[dr+R][dc+C].BlockTo(K);}
}

11. В клітинки, що містять нулі, при переборі варіантів потрібно буде записувати допустимі цифри і блокувати залежні клітинки (рядок, стовпець і квадратик) від встановлення такої самої цифри. Це реалізує метод Fill:

     void Fill (int r, int c, int K)
{  M[r][c].V=K;
for (int R=0; R<9; R++) if (R!=r) M[R][c].BlockTo(K);
for (int C=0; C<9; C++) if (C!=c) M[r][C].BlockTo(K);
int dr=r/3*3, dc=c/3*3;
for (int R=0; R<3; R++)
for (int C=0; C<3; C++)
if ((R!=r)&&(C!=c)) M[dr+R][dc+C].BlockTo(K);
}

12. При рекурсивному поверненні потрібно буде звільняти клітинки: встановлювати нуль і розблоковувати залежні клітинки:

     void Free (int r, int c, int K)
{  M[r][c].V=0;
for (int R=0; R<9; R++) if (R!=r) M[R][c].UnBlockTo(K);
for (int C=0; C<9; C++) if (C!=c) M[r][C].UnBlockTo(K);
int dr=r/3*3, dc=c/3*3;
for (int R=0; R<3; R++)
for (int C=0; C<3; C++)
if ((R!=r)&&(C!=c)) M[dr+R][dc+C].UnBlockTo(K);
}

13. Знайшовши розв'язок, потрібно його вивести у вихідний потік. Метод Write реалізує порядкове виведення цифр з масиву клітинок:

     void Write()
{  for (int r=0; r<9; r++)
{   f2<<M[r][0].V;
for (int c=1; c<9; c++)
{  f2<<' '<<M[r][c].V;
}
f2<<endl;
}
}

14. Далі - відкриті функції-члени класу field:

     public:

- конструктор, у якому відкриваються файлові потоки. Вхідні параметри - рядки з іменами файлів. У ньому дані зчитуються з вхідного файлу і розміщуються у масиві. При цьому "ненульові" клітинки жорстко блокуються (викликом методу FillHard):

field (char* fn1, char* fn2)
{ f1.open (fn1,ios::in); //відкриваємо вхідний файл
        for (int r=0; r<9; r++)
for (int c=0; c<9; c++)
{   int v;
f1>>v;
if (v!=0) FillHard(r,c,v);
}
f1.close (); //закриваємо вхідний файл

       f2.open (fn2,ios::out); //відкриваємо вихіднийфайл
     }

- деструктор, в якому закривається вихідний файл:

     ~field ()
{ f2.close ();
}

15. Розглянемо детальніше основний метод - Process - , в якому реалізується рекурсивний пошук варіантів заповнення. Вхідні параметри - номери рядка і стовпчика. Перегляд клітинок виконується по рядках:

     void Process(int r, int c)

При повторному виклику може виникнути потреба перейти на наступний рядок, тому зразу ж робимо відповідну перевірку і корекцію:

     {    if (c==9) {c=0; r++;}

Якщо після корекції вийшли за межі масиву, значить всі клітинки успішно заповнені цифрами і можна вивести результат:

          if (r==9) {Write(); return;}

Шукаємо клітинку, в якій записаний нуль:

          while ((r<9)&&M[r][c].V)
{ c++; if (c==9) {c=0; r++;}
}

Якщо знайшли, тобто номер рядка залишився в межах масиву,...

          if (r<9) {

...то пробуємо по черзі ставити в цю клітинку цифри, від яких вона не заблокована (метод Can).

for (int K=1; K<=9; K++)
if (M[r][c].Can(K))
{  Fill(r,c,K);

Поставивши цифру, повторюємо пошук, починаючи з наступної клітинки в рядку (рекурсивний виклик функції Process)

                          Process(r,c+1);

Якщо пошук у наступних клітинках завершився - знімаємо цю цифру і пробуємо поставити наступну (цикл for).

Free(r,c,K);
} // кінець циклу
}

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

          else {Write(); return;}
}
};

16. Праця, затрачена на розробку класів, дозволяє написати дуже коротку програму:

int main()
{

Створюємо об'єкт класу field, передавши йому імена файлів:

field *F= new field("sudoku.dat", "sudoku.sol");

Запускаємо процес пошуку розв'язку, починаючи з лівої верхньої клітинки поля:

   F->Process(0,0);
return 0;
}

Ось, власне, і все.

Трохи самокритики

Один з недоліків класу cell - використання прямого присвоєння значення полю V. Якщо надалі треба буде вдосконалити програму, додавши, наприклад, виведення клітинки на екран, то це буде зробити досить складно. Краще зробити поле V закритим, а для зміни цифри в клітинці додати відповідні методи у класі cell:
class cell {
int blocks [9];
int V;
public:
void SetNum (int v) {V=v;}
...
}
Після цього всі присвоєння виду M[r][c].V=K; замінити викликами методу M[r][c].SetNum(K);. В такому випадку, завдяки інкапсуляції, можна буде вдосконалювати програмний код, який виконується для зміни цифри (додати перемальовування на екрані, звукове оформлення, навіть підстрибування монітора ;) і т.п.), не втручаючись у написаний раніше програмний код класу field і не порушивши логічної цілісності коду класу cell.

Підсумок

1. Програма виявилась ефективною, і навіть судоку з журналу, яке містило всього 22 відомі цифри (тобто 59 нулів), розв'язала миттєво.
2. "Бонусом" програми є те, що вона коректно видає ВСІ варіанти заповнення "неправильного судоку", тобто такого, яке є неоднозначним (допускає кілька розв'язків). Зокрема, при одному з випробувань, доки автор розібрався що діється і зупинив програму, вона досить швиденько "набила" у файл біля 200 тисяч рядків цифр :).
Интернет реклама