Алгоритм генерации случайного игрового поля судоку.
Windows-приложение для вывода игрового поля на экран.
Цель работы: разработать программное средство, реализующее генерацию и решение кроссвордов судоку.
Задачи проекта:
1) изучить литературу;
2)отобрать компоненты и разобрать алгоритм для реализации программными средствами С++.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Судоку – это цифровая головоломка. Не надо гадать или копаться в книгах – только логика и внимательность.
Правила простые: заполнить пустые клетки цифрами от 1 до 9 так, чтобы в любой строке, любом столбце и в каждом из девяти блоков 3×3 цифры не повторялись. Это задача может быть и простой и невозможно сложной, в зависимости от предложенного варианта.
В зависимости от уровня сложности некоторые клетки уже содержат числа. Ваша задача - заполнить остальные клетки, используя Ваши серые клеточки. Необходимо обратить внимание на следующее правило: В игре участвую только числа с 1 до 9. Игровое поле (квадрат 9x9) должен быть заполнен таким образом, что, каждое число (с 1 до 9) встречается в каждой строке, в каждом столбце и в каждом малом квадрате (3x3) только один-единственный раз.
Пример решения:
Дана следующая головоломка (легкая), как показано на рисунке 1:
|
|
5 |
|
|
|
2 |
8 |
|
|
|
|
|
2 |
|
9 |
8 |
4 |
|
|
|
1 |
8 |
3 |
|
4 |
5 |
2 |
|
7 |
|
7 |
4 |
1 |
2 |
8 |
6 |
|
3 |
|
|
|
|
8 |
|
5 |
|
|
|
2 |
|
2 |
6 |
|
9 |
1 |
3 |
|
4 |
8 |
|
|
|
7 |
8 |
|
|
3 |
|
5 |
|
|
2 |
|
|
3 |
9 |
1 |
7 |
|
|
|
3 |
4 |
7 |
|
|
9 |
8 |
6 |
Рис. 1 Пример судоку 9×9
Шаг 1: Посмотрим на выделенный ряд. В нём не хватает только двух цифр: 5 и 9. Посмотрим на первую пустую клетку слева. Нельзя вписать 9, потому что в этой колонке цифра 9 уже есть, а повторяться цифры в колонке не могут. Значит, в эту клетку мы можем вписать лишь цифру 5. Теперь осталась вписать цифру 9 в последнюю пустую клетку чтобы этот ряд заполнился (рис. 2.).
Рис.2. Состояние судоку после первого шага
Шаг 2: Посмотрите на выделенную колонку: в ней не хватает всего двух цифр – 6 и 7. Цифру 6 мы не можем вписать в первую снизу клетку, потому что в пересекающем колонку ряду уже есть цифра 6. Впишем цифру 7. Цифру 6 впишем в оставшуюся клетку– вторая клетка снизу. Колонка заполнена(рис.3.).
Рис.3. Состояние судоку после второго шага
Шаг 3: Посмотрите на выделенный блок клеток: в нем осталась только одна пустая клетка. Впишем в неё цифру 1, так как все остальные цифры есть. После этого посмотрите: снова есть один ряд, в котором не хватает всего одной цифры (рис.4.).
Рис.4. Состояние судоку после третьего шага
Нужно повторять шаг1, шаг2, шаг3 пока все клетки не будут заполнены.
Если всё сделать правильно то получится (рис.5.).
Рис.5. Правильно решенный судоку
Программная реализация
#include "stdafx.h"
#include <algorithm> // std::random_shuffle
#include <time.h> // time
#include <iostream>
#include <cstdlib>
using namespace std;
// Массив судоку
int sudoku[9][9];
// Кандидаты на место в ячейке
int candidates[9][9][9];
// Маска для скрытия ячеек
int mask[81];
// Судоку со скрытыми ячейками
int pazzle[9][9];
// Счетчик итераций, потраченное на поиски судоку
int iteration_count;
void initCandidates();
void initCandidate(int i, int j);
int getCandidate(int i, int j);
bool testCandidate(int i, int j);
void applyMask();
void printSudoku(int sudoku[9][9]);
int main(array<System::String ^> ^args)
{
// Инициализация массива кандидатов
initCandidates();
// Значение текущего канжижата
int candidate_value;
// Номер текущей строки
int i = 0;
// Номер текущего столбца
int j = 0;
// Результат теста судоку
bool test_result = false;
// Цикл заполнения массива судоку
do{
// Цикл поиска валидного кандидата для текущей ячейки
do
{
// Получим значение кандидата для текущей ячейки
candidate_value = getCandidate(i, j);
sudoku[i][j] = candidate_value;
// Кандидатов для этой ячейки больше нет, тупик!
if (candidate_value == 0)
{
// И нам нужно востановить всех кандидатов для этой ячейки
initCandidate(i, j);
// Откатываемся назад на один шаг
if (j == 0)
{
j = 8;
i--;
}
else
j--;
sudoku[i][j] = 0;
break; // Выход из цикла поиска валидного кандидата для текущей ячейки
}
// проверяем кондидата по правилам судоку
test_result = testCandidate(i, j);
}while(test_result == false); // выполняем цикл до тех пор, пока не найдем валидного кандидата
//нашли кандидата
if (test_result == true)
{
// переходим к следующей ячейке
if (j == 8){
j = 0;
i++;
}
else
j++;
}
}while(sudoku[8][8] == 0); // Вы полянем цикл до тех пор, пока не заполним последний элемент массива судоку
// Применим маску для скрытия части ячеек
applyMask();
// Печатаем пазл
printSudoku(pazzle);
cout << "\r\n";
cout << "Iteration count: " << iteration_count;
cout << "\r\nPress [ENTER] to see solution. \r\n\r\n";
// Ждем нажатие клавиши
getchar();
// Печатаем решение судоку
printSudoku(sudoku);
getchar();
return 0;
}
// Инициализация всех кандидатов
void initCandidates()
{
std::srand(time(NULL));
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
initCandidate(i, j);
}
}
}
// Инициализация одной ячейки массива кандидатов значениями в случайном порядке
void initCandidate(int i, int j)
{
for (int k = 0; k < 9; k++)
{
candidates[i][j][k] = k+1;
}
std::random_shuffle(&candidates[i][j][0], &candidates[i][j][9]);
}
// Вернуть следующего кандидата для заданой ячейки
int getCandidate(int i, int j)
{
// проходим всех кандидатов для данной ячейки
for (int k = 0; k < 9; k++)
{
// обнуленные значения, которые мы уже отвергли, нас не интересуют
if (candidates[i][j][k] != 0)
{
// запоминаем значение кандидата
int candidate_value = candidates[i][j][k];
// удаляем его из кандидатов
candidates[i][j][k] = 0;
// возвращаем значение из фунцкии
return candidate_value;
}
}
return 0;
}
// Проверка последнего кандидата по правилам судоку
bool testCandidate(int i, int j)
{
int current_candidate = sudoku[i][j];
// Общий счетчик итераций
iteration_count++;
// Проверяем, есть ли еще такое значение в текущей строке
for (int p = 0; p < 9; p++)
{
if (p == j) continue;
if (sudoku[i][p] == current_candidate)
return false;
}
// Проверяем, есть ли еще такое значение в текущем столбце
for (int p = 0; p < 9; p++)
{
if (p == i) continue;
if (sudoku[p][j] == current_candidate)
return false;
}
// Проверяем, есть ли еще такое значение в текущем квадрате
int square_start_i = (int) i / 3 * 3; // Начало малого квадрата
int square_start_j = (int) j / 3 * 3;
int square_end_i = square_start_i + 3; // Конец малого квадрата
int square_end_j = square_start_j + 3;
for (int p = square_start_i; p < square_end_i; p++)
{
for (int m = square_start_j; m < square_end_j; m++)
{
if (p == i && m == j) continue;
if (sudoku[p][m] == current_candidate)
return false;
}
}
// Все тесты пройдены, этот кандидат подходит
return true;
}
void applyMask()
{
for(int i = 0; i < 20; i++)
mask[i] = 1;
std::random_shuffle(&mask[0], &mask[81]);
int m = 0;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
pazzle[i][j] = sudoku[i][j] * mask[m];
m++;
}
}
}
// Распечатать массив судоку на экран
void printSudoku(int sudoku[9][9]){
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (sudoku[i][j] != 0)
cout << sudoku[i][j] << " ";
else
cout << " ";
if ((j + 1) % 3 == 0 && j != 8)
cout << "|";
}
if ((i + 1) % 3 == 0 && i != 8)
cout << "\r\n-------------------";
cout << "\r\n";
}
}
ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ
При загрузке программы появляется генерированный кроссворд судоку. Немного ниже после надписи " Iteration count:" мы увидим число - счетчик итераций, потраченное на поиски судоку. Оно может быть разным, но в моем случае выпало 484. (Рис. 6).
Рис. 6. Генерированный судоку и счетчик итераций.
При нажатии клавиши "Enter" на экран выводиться решение прежде генерированного кроссворда судоку. (Рис. 7).
Рис. 7. Решение прежде генерированного кроссворда судоку.