Вівторок, 12.12.2017
Творча лабораторія

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


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

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

Нові статті

[17.09.2015] [Інформація]
Інформатика — місток між предметами
[20.05.2015] [Інформація]
Алгоритми і виконавці: безкомп’ютерний етап
[12.04.2015] [Навчальні посібники]
Авторська концепція комплекту «Інформатика. Базовий курс. 7 клас»

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


Розв'язуємо судоку - 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. "Бонусом" програми є те, що вона коректно видає ВСІ варіанти заповнення "неправильного судоку", тобто таких, які є неоднозначними (допускають кілька розв'язків).

4. У програмі не передбачена реакція на випадок, якщо головоломка не має розв'язку. Пропоную читачеві доробити програму самостійно, щоб у такому разі виводилося повідомлення "NO SOLUTION".

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

Підтримка
Ви можете підтримати цей проект:

WMR164778923006
WMZ277001591405

Система Orphus

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


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