Программа «Обход конем»

ВВЕДЕНИЕ

1. СИСТЕМНЫЙ АНАЛИЗ

1.1 Формулировка проблемной ситуации

1.2 Определение целей

1.3 Поиск оптимального варианта решения

1.4 Проверка эффективности решения

2. АНАЛИЗ ТРЕБОВАНИЙ

2.1 Формирование представления

2.2 Выявление требований

2.2.1 Требования к функциональным характеристикам

2.2.2 Требования к надежности

3. ПРОЕКТИРОВАНИЕ

3.1 Проектирование интерфейса

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

4. КОДИРОВАНИЕ

5. ТЕСТИРОВАНИЕ

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

ПРИЛОЖЕНИЯ

Приложение 1. Техническое задание

Приложение 2. Исходный код программы

ВВЕДЕНИЕ

В данной работе ставится задача разработки программы — обход конем. Имеется шахматная доска размером N*N, где N?50. Можно ли обойти ее конем из начальной позиции (h, v), побывав при этом на каждой клетке в точности один раз. Возможны два случая: а) в конце обхода конь возвращается в исходную позицию. б) конь завершает обход без возврата в исходную позицию. Определить, каким из вариантов можно совершить обход и можно ли вообще. Обязательна визуализация процесса и пошаговая демонстрация. Приложение разрабатывается на языке программирования C++ в интегрированной среде разработки Microsoft Visual Studio 2008.

1. СИСТЕМНЫЙ АНАЛИЗ

1.1 Формулировка проблемной ситуации Разработка программы «обход конем», с оформлением каждого этапа разработки в соответствующем разделе пояснительной записки.

1.2. Определение целей Перед разработчиком определены следующие цели:

Ознакомление с визуализацией программы.

Определение технических требований к программе.

Создание эффективного алгоритма для решения поставленной задачи с последующей его реализацией на языке программирования C++.

1.3 Поиск оптимального варианта решения Для решения задачи будет использован метод объектно-ориентированного программирования. Данная концепция позволит существенно упростить задачу, используя следующие подходы:

Инкапсуляция.

Скрыв большинство членов класса, можно быть уверенным, что состояние объекта не будет испорчено из вызывающей программы.

Быстрое прототипирование.

Данная возможность позволит описывать классы только их основными свойствами и поведением, что позволит сразу проверить главную идею решения поставленной задачи.

1.4 Проверка эффективности решения Использование объектно-ориентированного подхода к решению задачи позволит упростить процесс написания кода, а также решение ее с минимальным количеством ошибок, а также минимальной затратой времени.

2. АНАЛИЗ ТРЕБОВАНИЙ

2.1 Формирование представления Программа должна удовлетворять всем требованиям, приведенным в этом разделе.

2.2 Выявление требований

2.2.1 Требования к функциональным характеристикам Программа должна находить оптимальный путь обхода шахматной доски.

Программа должна генерировать доску размера, задаваемого пользователем.

Программа должна выводить визуализацию пошагового обхода доски.

2.2.2 Требования к надежности Программа должна предотвращать ошибочные действия пользователя.

Программа должна контролировать входную информацию.

3. ПРОЕКТИРОВАНИЕ

3.1 Проектирование интерфейса При построении данной программы, использовалась библиотек GLUT.

Описание библиотеки GLUT:

1. Инициализация GLUT производится командой:

void glutInit (int *argcp, char **argv);

Первый параметр представляет из себя указатель на количество аргументов в командной строке, а второй — указатель на массив аргументов. Обычно эти значения берутся из главной функции программы: int main (int argc, char *argv[]).

2. Установка параметров окна содержит в себе несколько этапов. Прежде всего необходимо указать размеры окна:

void glutInitWindowSize (int width, int height);

Первый параметр width — ширина окна в пикселях, второй height — высота окна в пикселях. Отмечу также, что если эту команду опустить, то GLUT сам установит размеры окна по умолчанию, обычно это 300×300.

Далее можно задать положение создаваемого окна относительно верхнего левого угла экрана. Делается это командой:

void glutInitWindowPosition (int x, int y);

Необходимо также установить для окна режим отображения информации. Т. е. установить для окна такие параметры как: используемая цветовая модель, количество различных буферов, и т. д. Для этого в GLUT существует команда:

void glutInitDisplayMode (unsigned int mode);

У команды имеется единственный параметр, который может быть представлен одной из следующих констант или комбинацией этих констант с помощью побитового ИЛИ.

3. Создание окна. После того как окно установлено необходимо его создать.

int glutCreateWindow (const char *title);

Эта команда создаёт окно с заголовком, который вы укажете в качестве параметра и возвращает HANDLER окна в виде числа int. Этот HANDLER обычно используется для последующих операций над этим окном, таких как изменение параметров окна и закрытие окна.

4. Установка функций, отвечающих за рисование в окне и изменении формы окна.

После того, как окно, в которое будет выводится или как говорят рендерится графическая информация, подготовлено и создано, необходимо связать с ним процедуры, которые будут отвечать за вывод графической информации, следить за размерами окна, следить за нажатиями на клавиши и т. д. Самая первая и самая необходимая функция которую мы рассмотрим, отвечает за рисование. Именно она всегда будет вызываться операционной системой, чтобы нарисовать (перерисовать) содержимое окна. Итак, задаётся эта функция командой:

void glutDisplayFunc (void (*func)(void));

Единственный параметр этой функции — это указатель на функцию, которая будет отвечать за рисование в окне. Например чтобы функция void Draw (void), определенная в вашей программе отвечала за рисование в окне, надо присоединить ее к GLUT следующим образом: glutDisplayFunc (Draw);

И ещё одна функция, которая по моему мнению является важной — это функция, которая отслеживает изменения окна. Как только у окна изменились размеры, необходимо перестроить вывод графической информации уже в новое окно с другими размерами. Если этого не сделать, то например увеличив размеры окна, вывод информации будет производиться в старую область окна, с меньшими размерами. Определить функцию, отвечающую за изменение размеров окна нужно следующей командой:

void glutReshapeFunc (void (*func)(int width, int height));

Единственный параметр — это указатель на функцию, отвечающую за изменение размеров окна, которая как видно должна принимать два параметра width и height, соответственно ширина и высота нового (измененного) окна.

5. Вход в главный цикл GLUT.

Ну и последнее, что необходимо сделать, чтобы запустить нашу программу — это войти в так называемый главный цикл GLUT. Этот цикл запускает на выполнение так называемое сердце GLUT, которое обеспечивает взаимосвязь между операционной системой и теми функциями, которые отвечают за окно, получают информацию от устройств ввода/вывода. Для того, чтобы перейти в главный цикл GLUT, надо выполнить единственную команду:

void glutMainLoop (void);

Программа состоит из одного окна, включающего:

glutInit (&argc, argv); для визуализации обхода.

Интерфейс программы продемонстрирован на Рисунке 1.

Рисунок 1. Главное окно программы

3.2 Описание алгоритмов Основным алгоритмом данной программы является правило Варнсдорфа: При обходе доски, конь следует на ту клетку, с которой можно пойти на минимальное число ещё не пройденных клеток. Если таких клеток несколько, то можно пойти на любую из них.

На Рисунке 2 наглядно представлен алгоритм работы программы.

Рисунок 2. Блок-схема программы

4. КОДИРОВАНИЕ Рассмотрим функцию нахождения пути обхода:

const struct

{

int dx;

int dy;

} moves[] =//Массив вариантов хода коня

{

{ -1, -2 },

{ 1, -2 },

{ -2, -1 },

{ 2, -1 },

{ -2, 1 },

{ 2, 1 },

{ -1, 2 },

{ 1, 2 }

};

multimap seq;//Массив, в который заносится пара значений

for (size_t i = 0; i < sizeof (moves) / sizeof (*moves); ++i) //Расчет вариантов ходов с возможных клеток

{

const int x0 = x + moves[i]. dx;

const int y0 = y + moves[i]. dy;

int c = 0;//Счетчик ходов

for (size_t j = 0; j < sizeof (moves) / sizeof (*moves); ++j)

{

const int x1 = x0 + moves[j]. dx;

const int y1 = y0 + moves[j]. dy;

if (x1 >= 0 && x1 < N &&//Проверка на выход за границы доски

y1 >= 0 && y1 < N &&

!board[x1][y1])//Проверка был ли конь на этой клетке

++c;

}

seq.insert (pair (c, i));

}

for (multimap:iterator i = seq. begin (); i ≠ seq. end (); ++i) //Переход на нужную клетку

{

const int x0 = x + moves[i -> second]. dx;

const int y0 = y + moves[i -> second]. dy;

if (x0 >= 0 && x0 < N &&//Проверка на выход за границы доски

y0 >= 0 && y0 < N &&//Проверка был ли конь на этой клетке

!board[x0][y0] && solve (x0, y0))

return true;

}

board[x][y] = false;

solution.pop_back ();

return false;

}

Рассмотрим функцию построения графического интерфейса:

void display ()//Функция построения графического интерфейса

{

glClear (GL_COLOR_BUFFER_BIT);

const int step = 480 / N;

glBegin (GL_QUADS);//Создание квадратов

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

{

if ((i + j) % 2)

glColor3f (0.5, 0.5, 0.5);

else

glColor3f (0, 0, 0);

const int x = i * step;

const int y = j * step;

glVertex2f (x, y);

glVertex2f (x + step, y);

glVertex2f (x + step, y + step);

glVertex2f (x, y + step);

}

glEnd ();

glPointSize (3);

glBegin (GL_POINTS); //Создание точек (обозначение коня на доске)

glColor3f (0, 1, 0);

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

if (board[i][j])

{

const int x = i * step + step / 2;

const int y = j * step + step / 2;

glVertex2f (x, y);

}

glEnd ();

glPointSize (1);

glBegin (GL_LINE_STRIP);//Создание линий, связывающих точки

for (vector:iterator i = solution. begin (); i ≠ solution. end (); ++i)

{

const int x = i -> x * step + step / 2;

const int y = i -> y * step + step / 2;

glVertex2f (x, y);

}

glEnd ();

glutSwapBuffers ();

}

5. ТЕСТИРОВАНИЕ В данной программе будем проводить тестирование графического интерфейса:

Для начала протестируем построение самой доски.

Создадим доску размером 8*8:

программа путь интерфейс алгоритм Рисунок 3. Изображение шахматной доски.

Протестируем построения точки:

Рисунок 4. Изображение точки на шахматной доске.

Проверим построение линий:

Рисунок 5. Изображение линии на шахматной доске.

Набор основных тестов пройден успешно, программа «Обход конем» работоспособна.

http://www.cyberforum.ru/cpp.

http://msdn.microsoft.com/ru-ru/library/60k1461a (v=VS.90).aspx

http://compgraphics.info/OpenGL/template_glut.php

C++ для начинающих. Серия «Шаг за шагом» / Г. Шилдт;

Приложение 1. Техническое задание Введение Наименование программы: Обход конем.

Применение: Нахождение оптимального пути обхода шахматной доски шахматным конем.

1.1 Основание для разработки Задание преподавателя для проведения лабораторных занятий и выполнения курсовой работы.

1.2 Назначение разработки Программа предназначена для нахождения пути обхода шахматной доски размером N*N от 5*5, до 40*40 шахматным конем.

1.3 Требования к программе

1.3.1 Требования к функциональным характеристикам Программа должна находить оптимальный путь обхода шахматной доски.

Программа должна генерировать доску размера N*N от 5*5 до 40*40, задаваемого пользователем.

Программа должна выводить визуализацию пошагового обхода доски.

1.3.2 Требования к надежности Некорректные действия пользователя должны пресекаться программой.

1.4 Требования к составу и параметрам технических средств Программное обеспечение должно работать на IBM-совместимых персональных компьютерах.

Минимальная конфигурация: тип процессора — Pentium III и выше; объем ОЗУ — 512 Мб и выше.

Наличие 10 Мб свободного пространства на диске.

ЭВМ должна работать под управлением операционной системы не ниже, чем Microsoft Windows XP.

1.5 Требования к информационной и программной совместимости Программа имеет совместимость с любой системой windows выше XP.

1.6 Условия эксплуатации Для начала работы необходимо подключить библиотеку GLUT.

1.7 Специальные требования Не предусмотрены.

1.8 Требования к программной документации Результаты выполнения курсовой работы оформлены в виде пояснительной записки. Пояснительная записка оформлена в соответствии с требованиями ГОСТ 19.404−79. ЕСПД.

1.9 Стадии и этапы разработки Разработка данной курсовой работы состоит из следующих этапов:

Постановка задачи Анализ способов решения поставленной задачи Выбор рационального способа решения Реализация выбранного способа Тестирование реализованного программного обеспечения и выводы об его универсальности и функциональности

1.10 Порядок контроля и приемки Составил:

Согласовано:

Приложение 2. Исходный код программы

#include «stdafx.h»

#include «glut.h»

#include

#include

using namespace std;

const int N = 40;//Размер поля

bool board[N][N]; //Массив, содержащий булевские знаения (true — конь на доске, и falce — конь отсутствует)

struct Position//Структура с позициями коня на доске

{

int x;

int y;

};

vector solution;//Вектор, содержащий позиции коня

void display ()//Функция построения графического интерфейса

{

glClear (GL_COLOR_BUFFER_BIT);

const int step = 480 / N;

glBegin (GL_QUADS);//Создание квадратов

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

{

if ((i + j) % 2)

glColor3f (0.5, 0.5, 0.5);

else

glColor3f (0, 0, 0);

const int x = i * step;

const int y = j * step;

glVertex2f (x, y);

glVertex2f (x + step, y);

glVertex2f (x + step, y + step);

glVertex2f (x, y + step);

}

glEnd ();

glPointSize (3);

glBegin (GL_POINTS);//Создание точек (обозначение коня на доске)

glColor3f (0, 1, 0);

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

if (board[i][j])

{

const int x = i * step + step / 2;

const int y = j * step + step / 2;

glVertex2f (x, y);

}

glEnd ();

glPointSize (1);

glBegin (GL_LINE_STRIP);//Создание линий, связывающих точки

for (vector:iterator i = solution. begin (); i ≠ solution. end (); ++i)

{

const int x = i -> x * step + step / 2;

const int y = i -> y * step + step / 2;

glVertex2f (x, y);

}

glEnd ();

glutSwapBuffers ();

}

bool solve (int x, int y)

{

board[x][y] = true;//Помещаем коня на доску

Position tmp = { x, y };

solution.push_back (tmp);

display ();

if (solution.size () == N * N)//Если размер массива принимает значение N*N, то решение найдено и доска полностью пройдена конем.

return true;

/*

.1.2.

3…4

.x.

5…6

.7.8.

*/

const struct

{

int dx;

int dy;

} moves[] =//Массив вариантов хода коня

{

{ -1, -2 },

{ 1, -2 },

{ -2, -1 },

{ 2, -1 },

{ -2, 1 },

{ 2, 1 },

{ -1, 2 },

{ 1, 2 }

};

multimap seq;//Массив, в который заносится пара значений

for (size_t i = 0; i < sizeof (moves) / sizeof (*moves); ++i) //Расчет вариантов ходов с возможных клеток

{

const int x0 = x + moves[i]. dx;

const int y0 = y + moves[i]. dy;

int c = 0;//Счетчик ходов

for (size_t j = 0; j < sizeof (moves) / sizeof (*moves); ++j)

{

const int x1 = x0 + moves[j]. dx;

const int y1 = y0 + moves[j]. dy;

if (x1 >= 0 && x1 < N &&//Проверка на выход за границы доски

y1 >= 0 && y1 < N &&

!board[x1][y1])//Проверка был ли конь на этой клетке

++c;

}

seq.insert (pair (c, i));

}

for (multimap:iterator i = seq. begin (); i ≠ seq. end (); ++i) //Переход на нужную клетку

{

const int x0 = x + moves[i -> second]. dx;

const int y0 = y + moves[i -> second]. dy;

if (x0 >= 0 && x0 < N &&//Проверка на выход за границы доски

y0 >= 0 && y0 < N &&

!board[x0][y0] &&//Проверка был ли конь на этой клетке

solve (x0, y0))

return true;

}

board[x][y] = false;

solution.pop_back ();

return false;

}

void timer (int = 0)//Очистка доски

{

for (int i = 0; i < N; ++i)

for (int j = 0; j < N; ++j)

board[i][j] = false;

solution.clear ();

solve (0, 0);

display ();

}

int main (int argc, char **argv)//Вывод на экран

GLUT_RGB);

glutInitWindowSize (480, 480);

glutInitWindowPosition (40, 450 — 450);

glutCreateWindow («Knight's tour»);

glClearColor (0, 0, 0, 1.0);

glMatrixMode (GL_PROJECTION);

glLoadIdentity ();

glOrtho (0, 480, 480, 0, -1, 1);

glutDisplayFunc (display);

glutTimerFunc (10, timer, 0);

glutMainLoop ();