Генерация и решение кроссвордов "Судоку"
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Челябинский Государственный Педагогический Университет
Кафедра информатики и методики преподавания информатики
Курсовая работа по программированию и программному обеспечению на тему:
ГЕНЕРАЦИЯ И РЕШЕНИЕ КРОССВОРДОВ "СУДОКУ"
Челябинск
Содержание
Введение. Описание программного продукта
Игра "СУДОКУ"
Пользовательский интерфейс. Реализация программного продукта
Общая схема форм
Описание алгоритма
Заключение
Список литературы
Введение
Родиной шахмат считается Индия, родиной футбола - Англия. У игры судоку (sudoku), быстро распространившейся по всему миру, родины как таковой нет. Прообразом судоку можно считать головоломку "Магический квадрат", которая появилась в Китае 2000 лет назад. Игра представляет собой квадрат размером 33 клетки. В каждую клетку помещается одно число от 1 до 9 причём так, чтобы сумма чисел в любом столбце, строке и по диагонали равнялась 15.
История судоку как игры восходит к имени знаменитого швейцарского математика, механика и физика Леонарда Эйлера (1707-1783). Исследуя различные варианты магического квадрата, Эйлер обратил внимание на проблему комбинации символов таким образом, чтобы не один из них не повторялся ни в одной строке и ни в одном столбце.
В современном виде головоломки судоку впервые были опубликованы в 1979 году в журнале Word Games magazine. Автором головоломки был Гарвард Гарис. Он использовал принцип латинского квадрата Эйлера, применил его в матрице размерностью 99 и добавил дополнительные ограничения, цифры не должны повторяться и во внутренних квадратах 33.
В названии Sudocu Su обозначает число, а doku-стоящая отдельно. Судоку называют кубиком Рубика 21 века, а также самой захватывающей головоломкой в мире.
Цель проекта: Разработать программное средство, реализующее генерацию и решение кроссвордов СУДОКУ.
Задачи проекта:
) изучить литературу;
)отобрать задачи судоку и разобрать алгоритм их решения;
)отобрать компоненты и разобрать алгоритм для реализации программными средствами Delphi.
I. Описание программного продукта
Игра "СУДОКУ"
Судоку - это цифровая головоломка. В переводе с японского "су" означает "цифра", а "доку"- "стоящая отдельно". Не надо гадать или копаться в книгах - только логика и внимательность.
Правила простые: заполнить пустые клетки цифрами от 1 до 9 так, чтобы в любой строке, любом столбце и в каждом из девяти блоков 33 цифры не повторялись.
Пример решения:
Дана следующая головоломка, как показано на рисунке 1:
5 28 2 984 183 452 7741286 3 8 5 226 913 48 78 3 5 2 3917 347 986Рис. 1 Пример судоку 99
Шаг 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. Правильно решенный судоку
Пользовательский интерфейс
При запуске программы появляется форма (рис.6.) . По умолчанию выбран легкий уровень сложности.
Рис.6. Форма
Выбрать уровень сложности можно в меню Игра > Уровень сложности "выпадет" подменю легкий, средний, сложный (рис.7.).
Рис.7. Выбор уровня
Уровень сложности определяется количеством пустых клеток в судоку.
При выборе легкого уровня появляется надпись "Вы выбрали уровень сложности легкий" Легкий уровень по умолчанию. (рис.8.).
Рис.8. Выбран легкий уровень
Аналогично, при выборе среднего уровня (рис.9.).
Рис.9. Выбран средний уровень
Аналогично, при выборе сложного уровня (рис.10.).
Рис.10. Выбран сложный уровень
При нажатии на кнопку "Генерация", появляется сам судоку (рис.12.).
Рис.11. Нажатие на кнопку "Генерация"
Можно решать судоку, ставить цифры в пустые ячейки от 1 до 9 (рис.12.).
Рис.12. Подстановка цифр
Проверку можно произвести, нажав на кнопку "Проверить" (рис.13.).
Рис.13. Проверка
При правильном решении судоку, появляется надпись "Молодец" (рис.14.).
Рис.14. Правильное решение судоку
При не правильном