Понеділок, 05.12.2022
Творча лабораторія

Навчальні посібники та робочі зошити з інформатики - якісно і дешево


Меню сайту
Реклама
Категорії каталогу
MS Visual C++ 2005 Express Edition [3]
Середовища програмування [8]
Особливості встановлення та використання різних середовищ програмування
MS Visual Basic 6 [1]
Microsoft Visual Basic
C# [8]
Програмування мовою C#
C++ [3]
Паскаль [5]
ЛОГО [1]
Олімпіадне програмування [0]
Python [1]
Головна » Статті » Програмування » C++

Розв'язуємо судоку - 2. Процедурний варіант.

Нові статті

[19.02.2020] [C#]
Задача про розрізання квадрата (ООП, C#)
[09.02.2020] [Python]
Задача про розрізання квадрата (ООП, Python)
[06.02.2020] [Паскаль]
Задача про розрізання квадрата (ООП, Free Pascal)

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

 

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

 

Процедурне програмування мовою C++

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

Нагадаю суть головоломки. Дано квадратну таблицю, в деякі клітинки якої вписані цифри. Наприклад:
 

судоку


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

 

Ідея

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

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

 

 

  1. перебираючи цифри за рядками, знайти нуль;
  2. якщо нуля знайти не вдалося - задача розв'язана :). Кінець.
  3. для кожної з цифр, які можна поставити в дану клітинку:
    • записати в клітинку цю цифру;
    • перейти до пункту 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".

 


Интернет реклама
Категорія: C++ | Додав: teachlab (16.01.2009)
Переглядів: 3482 | Рейтинг: 0.0/0
Всього коментарів: 0
Додавати коментарі можуть тільки зареєстровані користувачі.
[ Реєстрація | Вхід ]
Форма входу
Пошук
Друзі сайту

Підтримка

Система Orphus

Маєте свій сайт?
Заробіть на ньому грошей!


Не маєте власного сайту?
Заробіть на обміні файлами!
Статистика
Copyright Пилипчук О.П. © 2022
div id=