Генерация и решение кроссвордов 'Судоку'

Челябинский Государственный Педагогический Университет

Кафедра информатики и методики преподавания информатики

Курсовая работа по программированию и программному обеспечению на тему:

ГЕНЕРАЦИЯ И РЕШЕНИЕ КРОССВОРДОВ "СУДОКУ"

Челябинск

Содержание

Введение. Описание программного продукта

Игра "СУДОКУ"

Пользовательский интерфейс. Реализация программного продукта

Общая схема форм

Описание алгоритма

Заключение

Список литературы

Введение

Родиной шахмат считается Индия, родиной футбола - Англия. У игры судоку (sudoku), быстро распространившейся по всему миру, родины как таковой нет. Прообразом судоку можно считать головоломку "Магический квадрат", которая появилась в Китае 2000 лет назад. Игра представляет собой квадрат размером 3×3 клетки. В каждую клетку помещается одно число от 1 до 9 причём так, чтобы сумма чисел в любом столбце, строке и по диагонали равнялась 15.

История судоку как игры восходит к имени знаменитого швейцарского математика, механика и физика Леонарда Эйлера (1707-1783). Исследуя различные варианты магического квадрата, Эйлер обратил внимание на проблему комбинации символов таким образом, чтобы не один из них не повторялся ни в одной строке и ни в одном столбце.

В современном виде головоломки судоку впервые были опубликованы в 1979 году в журнале Word Games magazine. Автором головоломки был Гарвард Гарис. Он использовал принцип латинского квадрата Эйлера, применил его в матрице размерностью 9×9 и добавил дополнительные ограничения, цифры не должны повторяться и во внутренних квадратах 3×3.

В названии Sudocu Su обозначает число, а doku-стоящая отдельно. Судоку называют кубиком Рубика 21 века, а также самой захватывающей головоломкой в мире.

Цель проекта: Разработать программное средство, реализующее генерацию и решение кроссвордов СУДОКУ.

Задачи проекта:

) изучить литературу;

)отобрать задачи судоку и разобрать алгоритм их решения;

)отобрать компоненты и разобрать алгоритм для реализации программными средствами Delphi.

I. Описание программного продукта

Игра "СУДОКУ"

Судоку - это цифровая головоломка. В переводе с японского "су" означает "цифра", а "доку"- "стоящая отдельно". Не надо гадать или копаться в книгах - только логика и внимательность.

Правила простые: заполнить пустые клетки цифрами от 1 до 9 так, чтобы в любой строке, любом столбце и в каждом из девяти блоков 3×3 цифры не повторялись.

Пример решения:

Дана следующая головоломка, как показано на рисунке 1:

Рис. 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. Правильно решенный судоку

Пользовательский интерфейс

При запуске программы появляется форма (рис.6.) . По умолчанию выбран легкий уровень сложности.

Рис.6. Форма

Выбрать уровень сложности можно в меню Игра → Уровень сложности "выпадет" подменю легкий, средний, сложный (рис.7.).

Рис.7. Выбор уровня

Уровень сложности определяется количеством пустых клеток в судоку.

При выборе легкого уровня появляется надпись "Вы выбрали уровень сложности легкий" Легкий уровень по умолчанию. (рис.8.).

Рис.8. Выбран легкий уровень

Аналогично, при выборе среднего уровня (рис.9.).

Рис.9. Выбран средний уровень

Аналогично, при выборе сложного уровня (рис.10.).

Рис.10. Выбран сложный уровень

При нажатии на кнопку "Генерация", появляется сам судоку (рис.12.).

Рис.11. Нажатие на кнопку "Генерация"

Можно решать судоку, ставить цифры в пустые ячейки от 1 до 9 (рис.12.).

Рис.12. Подстановка цифр

Проверку можно произвести, нажав на кнопку "Проверить" (рис.13.).

Рис.13. Проверка

При правильном решении судоку, появляется надпись "Молодец" (рис.14.).

Рис.14. Правильное решение судоку

При не правильном решении появится надпись "Попробуйте еще" (рис.15.).

Рис.15. Не правильное решение судоку

Для того, чтобы изменить размер шрифта, нужно зайти в меню Настройки →Шрифт и выберите мелкий, средний или крупный. По умолчанию стоит средний(рис.16.).

Рис.16. Изменение размера шрифта

Для того, чтобы сохранить игры, нужно зайти в меню Игра→запомнить (рис.17).

Рис.17. Сохранение игры

Открыть ранее сохраненную игру можно, если зайти в меню Игра→открыть (рис.18).

Рис.18. Открытие ранее сохраненной игры

Информация об авторе можно узнать в меню Помощь→ Об авторе (рис.19.).

Рис.19. Информация об авторе

Правила игры можно узнать в меню Помощь→ Об игре (рис.20.).

Рис.20. Правила игры

Для того, чтобы выйти из игры нужно зайти в меню Игра→ Выход (рис.21.).

Рис.21.Выход из игры

II. Реализация программного продукта

Общая схема форм

Компоненты, размещенные на форме Form1 (рис.22.).

Рис.22. Компоненты, расположенные на Form1

) Button1 - кнопка "Генерация" (для генерирования судоку);

) Button2 - кнопка "Проверка" (для проверки решения);

3) Edit1 - для отображения выбранного уровня сложности;

) Image1 - для отображения картинки (дизайн);

) Label1 - отображение надписи "Вы выбрали уровень сложности";

) Label2 -вывод результата проверки (или "Молодец" если правильно, или "Попробуй еще" если не правильно);

7) MainMenu1 - для меню;

8) OpenDialog1 - открытие ранее сохраненной игры;

)Panel1 -панель, на которой размещаются динамически создаваемые Edit;

) SaveDialog1 - для сохранения программы.

Компоненты, размещенные на форме AboutBox (рис.23.).

Рис.23. Компонент, расположенный на AboutBox

) OKButton - кнопка для выхода из AboutBox;

) Panel1 - панель, на которой размещена информация об авторе.

Компоненты, размещенные на форме AboutBox1 (рис.24.).

Рис.24. Компоненты, расположенные на AboutBox1

1) OKButton - кнопка для выхода из AboutBox1;

)Panel1 - панель, на которой размещены правила игры.

Описание алгоритма

Цифровая головоломка судоку 9×9 состоит из 81 клеток, которые делятся на 9 блоков 3×3. В данной программе функции клеток будут выполнять Edit.

Для этого глобально опишем массив из Edit :

: array [1..81] of Tedit; //массив из Edit9o:string[81]; //строка, в которой хранятся ответы на судоку

filename:string; //имя файла, в котором хранятся судоку

ansfilename:string; // имя файла, в котором хранятся ответы на судоку из файла filename,g:TextFile; //текстовые файлы, в которых судоку:char;//символ из текстового файла

Еdit создаются динамически на панеле Panel1. Процедура Tform1.Ed_clean удаляет и заново создает Рanel1:

TForm1.Ed_clean;:Tpanel; // панель

begin.Free; // очищаем панель:=Tpanel.Create(self); // создаем "независимую панель".Parent:=form1;.Width:=521; // задаем ширину.Height:=353; // задаем длину.Name:='Panel1';.Caption:='';.Top:=136; // задаем вершину.Left:=24; // отступ слева;

Процедура TForm1.NewGame создает Edit на панели:

TForm1.NewGame;,j,n,l,k:byte;

Ed_clean; // вызываем процедуру Tform1.Ed_clean, которая создает панель

n:=1; // счетчикi:=1 to 11 do // i - количество строк j:=1 to 11 do // j - количество столбцов

begin((i<>4) and (j<>4)) and ((i<>8) and (j<>8))then[n]:=Tedit.Create(self); //создаем Edit9[n].Parent:=Panel1; // помещаем его на панель

n:=n+1; // прибавляем счетчик; end;;

Для того, чтобы ограничить ввод символов, существует процедура Tform1.myKP9:

Tform1.myKP9(Sender: TObject; var Key: Char); not (Key in ['0'..'9']) then Key:='0'; // если ввели цифры, отличные от множества 0..9, значение присваиваем "0"

if ((Sender as Tedit).Tag)<>1 then

(Sender as Tedit).Text:=Key; // присваиваем значению нажатой кнопки:=#0;;

Начать новую игру инициирует процедура TForm1.Button1Click, которая запускается щелчком на кнопке Генерация.

TForm1.Button1Click(Sender: TObject);:byte;:string;; // запускается генератор случайных чисел

NewGame; // вызывается процедура TForm1.NewGame, которая создает Edit на панели

buf:=IntToStr(random(9)+1); // случайное число от 1 до 10

If Edit1.Text='' then Edit1.Text:='легкий'; // по умолчанию уровень сложности легкий.

if Edit1.Text='легкий' then Если уровень сложности легкий

begin:='eas/'+buf+'.txt'; // переменной присваиваем путь к файлу с судоку

ansfilename:='eas/ans/'+buf+'.txt'; // переменной присваиваем путь к файлу с ответами к судоку

end;Edit1.Text='средний' then:='sred/'+buf+'.txt'; // переменной присваиваем путь к файлу с судоку

ansfilename:='sred/ans/'+buf+'.txt'; // переменной присваиваем путь к файлу с ответами к судоку

end;Edit1.Text='сложный' then:='hard/'+buf+'.txt'; // переменной присваиваем путь к файлу с судоку

ansfilename:='hard/ans/'+buf+'.txt'; // переменной присваиваем путь к файлу с ответами к судоку

end;(f,filename); // связываем(f); // открываем файл:=1; not EOF(f) do // пока не конец файла

begin(f,t); // считываем их файла f t

if (t<>#13) and (t<>#10) then // если не Enter и не признак конца строки

c9[i].Text:=t; // присваиваем элементу массива (Edit) значение t

if t<>'0' then c9[i].Tag:=1c9[i].Tag:=0;:=i+1;;;(f);i:=1 to 81 doc9[i].Text='0' then[i].Text:='';(g,ansfilename);(g);o:= '';not EOF(g) do(g,buf);o:=c9o+buf;

end;(g);;

Проверку решения инициирует процедура TForm1.Button2Click, которая запускается щелчком на кнопке Проверка.

TForm1.Button2Click(Sender: TObject);:boolean;:byte;:=true;i:=1 to 81 do c9[i].Text<>c9o[i] then // сравнивает значение Edit со значением ответов

begin:=false;[i].Text:=''; // если ОК , тогда Edit =" ";ok then.caption:='Молодец'.caption:='Попробуйте ещё';

end;

Заключение

головоломка судоку алгоритм интерфейс

В ходе работы удалось реализовать все поставленные задачи и прийти к достойному решению. Литература изучена, отобраны задачи судоку и разобран алгоритм их решения, отобраны компоненты и разобран алгоритм для реализации программными средствами Delphi. Удалось создать программный продукт, являющийся красивым решением задачи, поставленной для выполнения данной курсовой работы. Работа может служить исходным материалом для последующей модернизации и совершенствования цифровой головоломки судоку.

Список литературы

1. Архангельский А.Я. "Программирование в Delphi 5 - 2-е изд., переработ. и дополн.", "Издательство БИНОМ", 2000г. -1072 с.;

. Журнал "СУДОКУ" спецвыпуск газеты "Япончик" №5 февраль, "Нижполиграф": 2008 г. - 48с.;

. Журнал "СУДОКУ" спецвыпуск газеты "Япончик" №9 март, "Нижполиграф": 2008 г. - 48 с.;

. Википедия - "http://ru.wikipedia.org/wiki/%D0%A1%D1%83%D0%B4%D0%BE%D0%BA%D1%83";