Пилипчук О.П., вчитель інформатики Гаврилівської ЗОШ Теофіпольського району Хмельницької області
Розв'язуємо судоку - 2
Процедурне програмування мовою C++
На противагу попередньому матеріалу, програма, розробка якої описана тут, витримана в процедурному стилі. Програміст сам обирає, в якому стилі писати програму, спираючись при цьому на перспективи проекту: об'єктноорієнтований підхід робить проект придатним для подальшого розвитку, а процедурний досить часто дозволяє швидше отримати розв'язок конкретної задачі.
Нагадаю суть головоломки. Дано квадратну таблицю, в деякі клітинки якої вписані цифри. Наприклад:
Потрібно заповнити порожні клітинки цифрами так, щоб кожен рядок, кожен стовпець і кожен з виділених на малюнку квадратів розміром 3*3 містили всі цифри від 1 до 9.
Ідея
Як і в попередньому матеріалі, розв'язок шукатимемо перебором можливих варіантів розставляння цифр. Якщо в процесі перебору буде знайдено розв'язок - просто виведемо його.
Загальний алгоритм такий:
- перебираючи цифри за рядками, знайти нуль;
- якщо нуля знайти не вдалося - задача розв'язана :). Кінець.
- для кожної з цифр, які можна поставити в дану клітинку:
- записати в клітинку цю цифру;
- перейти до пункту 1.
Розробка проекту
Примітка. Якщо з подальшого тексту вилучити пояснення - повинна залишитися працездатна програма.
1. Умова задачі передбачає файлове введення/виведення, тому слід підключити відповідну бібліотеку:
#include <fstream>
using namespace std;
2. Опишемо масив, який буде моделлю ігрового поля:
int M[9][9];
3. Розробимо функцію PrintRes()для виведення знайденого розв'язку у вихідний файл.
ofstream f2 ("sudoku.sol");
void PrintRes() {
for (int r=0; r<9; r++) {
for (int c=0; c<9; c++)
f2<<M[r][c]<<' ';
f2<<endl;
}
f2<<endl;
};
Останній розрив рядка ( endl;) виводиться на випадок, якщо вхідні дані некоректні і головоломка має кілька розв'язків. Якщо ж головоломка коректна, то це виведення можна вилучити з програми.
4. Функція Can(int R,int C,int K) для перевірки того, чи можна у клітинку на перетині рядка R (0<=R<=8) і стовпця C (0<=C<=8) поставити число K. Алгоритм цілком прозорий :)
bool Can(int R,int C,int K) {
bool rez=true;
for (int r=0; r<9; r++) //перевірка в рядку
if (M[r][C]==K) rez=false;
for (int c=0; c<9; c++) //перевірка у стовпці
if (M[R][c]==K) rez=false;
for (int r=0; r<3; r++) //перевірка у квадратику
for (int c=0; c<3; c++)
if (M[R/3*3+r][C/3*3+c]==K) rez=false;
return rez;
};
5. Рекурсивна функція Recurs(int R, int C), власне, й розв'язує задачу. Рядок за рядком комп'ютер шукає у масиві нулі. Знайшовши - пробує ставити в клітинку по черзі всі можливі цифри і робить рекурсивний виклик, щоб подивитися, що з цього вийде... При першому і подальших рекурсивних викликах робиться низка перевірок:
void Recurs(int R, int C)
{
if (R==9) PrintRes(); //рядки закінчились - отже розв'язок знайдено
else if (C==9) Recurs(R+1,0); //закінчився рядок - перейти на початок наступного
else if (M[R][C]!=0) Recurs(R,C+1); //дана клітинка не порожня - перейти до наступної
else {for (int K=1; K<10; K++) //перебираємо цифри від 1 до 9
{if (Can(R,C,K)) //якщо можна ставити цифру К
{M[R][C]=K; //то ставимо
Recurs(R,C+1);} //і переходимо до наступної клітинки,
} //а випробувавши всі цифри...
M[R][C]=0; //повертаємо на місце нуль.
}
return;
}
6. А ось і головна функція, ...
int main()
{
...в якій читаємо дані з вхідного файлу...
ifstream f1 ("sudoku.dat");
for (int r=0; r<9; r++)
for (int c=0; c<9; c++)
f1>>M[r][c];
... і викликаємо функцію, яка розв'яже нам задачу ;)
Recurs(0,0);
return 0;
}
Підсумок
1. Програма виявилась ефективною і опубліковане в журналі судоку, яке містило всього 22 відомі цифри (тобто 59 нулів), розв'язала миттєво.
2. "Бонусом" програми є те, що вона коректно видає ВСІ варіанти заповнення "неправильного судоку", тобто таких, які є неоднозначними (допускають кілька розв'язків).
3. У програмі не передбачена реакція на випадок, якщо головоломка не має розв'язку. Пропоную читачеві доробити програму самостійно, щоб у такому разі виводилося повідомлення "NO SOLUTION".
Интернет реклама
