Проектирование игры в шахматы

Министерство образования и наук Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ Курсовая работа по практикуму на ЭВМ: Структуры данных и алгоритмы Факультет прикладной математики и информатики Группа ПМИ-22

Студентка Малыгина Д.Н.

Преподаватель Тракимус Ю.В.

Новосибирск

1. Условие задачи

Задано описание шахматной позиции в обычной шахматной нотации. Например, «белые: Кр g1, Л f1, пп f2, g2, h3; чёрные: Кр b8, К e5, С e6, Ф a2, пп a7, b7». По описанию позиции напечатать изображение этой позиции, содержащее поле, разбитое на клетки подходящего размера, внутри которых записано название фигуры и её цвет (для занятых в позиции клеток). Определить все возможные ходы фигур. Переместить фигуру на возможное для неё место. шахматная позиция фигура ход

2. Анализ задачи

2.1 Исходные данные задачи

C = (B, W)

C — (описание шахматной позиции) сложная величина состоящая из 2-х эл. B и W

B = (N, Fj, Ki)? {? }

B — (фигуры чёрного цвета) сложная величина состоящая из 2-х эл. F, K или пустого множества

Fj — шахматная фигура j = 1, 16

Ki = (Xi, Yj) Ki — координата шахматной фигуры i = 1, 64

Xi? {`a', …, `h'} i = 1, 8 координата по x

Yj? {`1', …, `8'} j = 1, 8 координата по y

W = (N, Fj, Ki)? {? }

W — (фигуры белого цвета) сложная величина состоящая из 2-х эл. F, K или пустого множества

Fj — шахматная фигура j = 1, 16

Ki = (Xi, Yj) Ki — координата шахматной фигуры i = 1, 64

Xi? {`a', …, `h'} i = 1, 8 координата по x

Yj? {`1', …, `8'} j = 1, 8 координата по y

2.2 Результат

D = (T, n)? {? }

D — сложная величина состоящая из 2-х эл. или пустого множества

T = ti

Т — вид в котором шахматная фигура, включая её координаты, представлена в таблице

Ns — номер шахматной фигуры, под которым она обозначена в в таблице s = 1,32

Xj — номер под которым координата по X, шахматной фигуры, обозначена в в таблицеj = 1, 8

Yi — номер под которым координата по Y, шахматной фигуры, в таблицеi = 1, 8

n — величина обозначающая фактическое количество элементов Т, n = 1,32

2.3 Решение

Основное решение поставленной задачи составит в нахождении соответствующих значений входной величины т. е. все возможные варианты ходов фигуры

Формальная постановка задачи

— определение фигуры (сама фигура, цвет)

— в зависимости от определённой фигуры, выбор одного из нескольких алгоритмов решения

— изменение итоговых данных

3. Структуры исходных данных и результатов задачи

3.1 Входные данные

Внешнее представление:

С - описание шахматной позиции, представлена в виде 2-х элементов отделённых друг от друга '; '

1 элемент: В — фигуры чёрного цвета, состоит из 2-х элементов отделённых друг от друга запятыми и пробелами

1 эл. F — шахматная фигура (последовательность заглавных, строчных букв не более чем из 2-х символов)

2 эл. K — координата шахматной фигуры (последовательность из 2-х символов:

первый — строчная латинская буква, второй — цифра)

2 элемент: W — фигуры белого цвета, состоит из 2-х элементов отделённых друг от друга запятыми и пробелами

1 эл. F — шахматная фигура (последовательность заглавных, строчных букв не более чем из 2-х символов)

2 эл. K — координата шахматной фигуры (последовательность из 2-х символов:

первый — строчная латинская буква, второй — цифра)

Внутреннее представление:

С представлено, по частям в виде символьного массива

3.2 Выходные данные

Внешнее представление:

Изображение, на котором представлена шахматная доска с шахматными фигурами белого и чёрного цветов

Внутреннее представление:

Статическая таблица, состоящая из двух частей:

1-я часть список из трёх эл. (номер фигуры, координата по Х, координата по Y)

2-я часть n — фактическое количество эл. в таблице

— структура таблицы

struct elem

{

int chessmanNo;

int x;

int y;

}

struct work

{

elem table [32];

int n;

}

4. Укрупнённый алгоритм решения задачи

{

flg = 0;

if (выбор фигуры)

{

if (белые)

flg = 1;

if (королль)

//возможные ходы

king (a, b, flg);

if (ферзь)

//возможные ходы

queen (a, b, flg);

if (слон)

//возможные ходы

bishop (a, b, flg);

if (ладья)

//возможные ходы

rook (a, b, flg);

if (конь)

//возможные ходы

kNight (a, b, flg);

if (пешка)

//возможные ходы

pawn (a, b, flg);

}

//перенос выбраной фигуры

else

{

if (место занято) срубить фигуру;

else

переместить фигуру;

}

}

5. Структура программы

Текст программы разбит на четыре модуля.

Модуль 1 содержит функции решения основных подзадач и определения входных и выходных данных.

Модуль 2 содержит функции графического вывода данных.

Модуль 3 содержит объявление структур и подпрограмм.

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

5.1 Модуль 1

Главная функция main:

— назначение:

определения входных и выходных данных задачи.

— прототип: void main ()

5.2 Модуль 2

процедура input_fl

— назначение:

ввод из файла обозначения фигур привычных пользователю инициализация структур: color₁, color₂

— прототип: void input_fl (color₁ *B, color₂ *W)

процедура initchess

— назначение:

инициализация шахматных фигур (фигуры видные пользователю)

— прототип: void initchess ()

процедура figchess

— назначение: задаем место фигуры на изображении видном пользователю

iфигура, y, x — координаты

— прототип: void figchess (int i, int y, int x)

процедура myalg

— назначение: подпрограмма связывающая алгоритм решения задачи и вывод результата

— прототип: void myalg ()

процедура InitializeComponent

— назначение: инициализация компонент относящихся к выводу результата

— прототип: void InitializeComponent (void)

процедура clik

— назначение: подпрограмма связывающая нахождение возможных ходов

— прототип: void clik (int a, int b, stack **course)

5.3 Модуль 3

содержит объявление структур: color₁, color₂ (структуры содержащие обозначение фигур удобных пользователю и их соответствующее обозначения в программе),

work (таблица содержащая результат), stack (стек для хранения возможных ходов) содержит объявление процедур: myscanf, king, queen, bishop, rook, kNight, pawn, in_stack

содержит объявление функций: occupied_space, out_stack

5.4 Модуль 4

функция searchBlack

— назначение: поиск номера, соответствующего шахматной фигуре, под которые данная фигура известна программе

— прототип: searchBlack (char *s, color₁ B)

B — объявление структуры содержащей информацию о фигурах чёрного цвета (входной параметр)

s — символьный массив содержащий обозначение фигуры данная функция возвращает номер под которые данная фигура известна программе функция searchWhite

— назначение: поиск номера, соответствующего шахматной фигуре, под которые данная фигура известна программе

— прототип: int searchWhite (char *s, color₂ W)

W — объявление структуры содержащей информацию о фигурах белого цвета (входной параметр)

s — символьный массив содержащий обозначение фигуры данная функция возвращает номер под которыми данная фигура известна программе процедура myscanf

— назначение: считывание пользовательского обозначения фигур

— прототип: void myscanf (color₁ B, color₂ W, work *el)

возвращает указатель на таблицу с основным результатом программы процедура king

— назначение: определение возможных ходов короля

— прототип: void king (stack **B, int a, int c, int f, work ell)

процедура queen

— назначение: определение возможных ходов ферзя

— прототип: void queen (stack **B, int a, int c, int f, work ell)

процедура bishop

— назначение: определение возможных ходов слона

— прототип: void bishop (stack **B, int a, int c, int f, work ell)

процедура rook

— назначение: определение возможных ходов ладьи

— прототип: void rook (stack **B, int a, int c, int f, work ell)

процедура kNight

— назначение: определение возможных ходов коня

— прототип: void kNight (stack **B, int a, int c, int f, work ell)

процедура pawn

— назначение: определение возможных ходов пешки

— прототип: void pawn (stack **B, int a, int c, int f, work ell)

процедура in_stack

— назначение: операция положить в стек

— прототип: void in_stack (stack **Q, int x₁, int y₁)

функция out_stack

— назначение: операция положить в стек

— прототип: int out_stack (stack**Q, int *x₁, int *y₁)

5.5 Структура программы по управлению

6. Текст программы

/*chessman.h*/

#include «StdAfx.h»

#include

#include

#include

#include «chessman.h»

FILE *fl, *fll, *fll2, *input;

//Координаты по x

char x [] = «abcdefgh» ;

//Координаты по y

char y [] = «87 654 321» ;

void openfile (work ell)

{

if ((fll = fopen («fll.txt», «w»)) == NULL)

perror («error»);

else{

for (int i = 0; i<= ell. n; i++){

fprintf (fll," %d «, ell. table[i]. chessmanNo);

fprintf (fll," %d «, ell. table[i]. x);

fprintf (fll," %d «, ell. table[i]. y);

}

fclose (fll);

}

}

void closefile (work *ell)

{

if ((fll = fopen («fll.txt», «r»)) == NULL)

perror («error»);

else{

for (int i = 0; fscanf (fll," %d «,&(ell->table[i]. chessmanNo)) ≠ EOF; i++){

fscanf (fll," %d «,&(ell->table[i]. x));

fscanf (fll," %d «,&(ell->table[i]. y));

ell->n = i;

}

fclose (fll);

}

}

void openfile_stakc (stack **B)

{

if ((fll2 = fopen («fll2.txt», «w»)) == NULL)

perror («error»);

else{

int f, v;

while (out_stack (&(*B), &f, &v)){

fprintf (fll," %d «, f);

fprintf (fll," %dn", v);

}

fclose (fll2);

}

}

void closefil_stakc (stack **B)

{

if ((fll2 = fopen («fll2.txt», «r»)) == NULL)

perror («error»);

else{

int p, r;

while (fscanf (fll2," %d «,&p) ≠ EOF){

fscanf (fll," %d «,&r);

in_stack (&(*B), p, r);

}

fclose (fll2);

}

}

//поиск по чёрным фигурам

int searchBlack (char *s, color₁ B)

{

for (int k = 0; k<16; k++){

if (!strcmp (B.Bcolor[k]. chessman, s))

return B. Bcolor[k]. No;

}

return -1;

}

//поиск по белым фигурам

int searchWhite (char *s, color₂ W)

{

for (int k = 0; k<16; k++){

if (!strcmp (W.Wcolor[k]. chessman, s))

return W. Wcolor[k]. No;

}

return -1;

}

//считывание обозначение пользователя

void myscanf (color₁ B, color₂ W, work *el)

{

if ((input = fopen («input.txt», «r»)) == NULL)

perror («error»);

else{

int wrk, i;

el->n = 0;

char sym[5], chessm[3], chessman[3], slovo[8], same = '0', sign[] = «;» ;

// Считываем информацию о фигурах из файла

while (fscanf (input," %s" ,&slovo) ≠ EOF)

{

//чёрные фигуры

if (strcmp (B.chessBlack, slovo) == 0)

{

//считываем до ;

fscanf (input," %s" ,&sym);

while (sym[0] ≠ sign[0])

{

// координата

if (sym[1] >= '0' && sym[1] <= '9')

{

//если одинаковые фигуры

if (same ≠ '0')

{

strcpy (chessm, chessman);

strcat (chessm,&same);

wrk = searchBlack (chessm, B);

el->table[el->n]. chessmanNo = wrk;

//выясняем координату по x

i = 0;

while (sym[0] ≠ x[i])

i++;

el->table[el->n]. x = i;

//выясняем координату по y

i = 0;

while (sym[1] ≠ y[i])

i++;

el->table[el->n]. y = i;

//переходим к следующему элементу таблицы

el->n++;

same++;

}

else

{

//выясняем координату по x

i = 0;

while (sym[0] ≠ x[i])

i++;

el->table[el->n]. x = i;

//выясняем координату по y

i = 0;

while (sym[1] ≠ y[i])

i++;

el->table[el->n]. y = i;

//переходим к следующему элементу таблицы

el->n++;

same++;

}

}

//фигура

else

{

wrk = searchBlack (sym, B);

el->table[el->n]. chessmanNo = wrk;

same = '0';

strcpy (chessman, sym);

}

fscanf (input," %s" ,&sym);

}

}

//белые фигуры

else

{

//считываем до ;

fscanf (input," %s" ,&sym);

while (sym[0] ≠ sign[0])

{

// координата

if (sym[1] >= '0' && sym[1] <= '9')

{

//если одинаковые фигуры

if (same ≠ '0')

{

strcpy (chessm, chessman);

strcat (chessm,&same);

wrk = searchWhite (chessm, W);

el->table[el->n]. chessmanNo = wrk;

//выясняем координату по x

i = 0;

while (sym[0] ≠ x[i])

i++;

el->table[el->n]. x = i;

//выясняем координату по y

i = 0;

while (sym[1] ≠ y[i])

i++;

el->table[el->n]. y = i;

//переходим к следующему элементу таблицы

el->n++;

same++;

}

else

{

//выясняем координату по x

i = 0;

while (sym[0] ≠ x[i])

i++;

el->table[el->n]. x = i;

//выясняем координату по y

i = 0;

while (sym[1] ≠ y[i])

i++;

el->table[el->n]. y = i;

//переходим к следующему элементу таблицы

el->n++;

same++;

}

}

//фигура

else

{

wrk = searchWhite (sym, W);

el->table[el->n]. chessmanNo = wrk;

same = '0';

strcpy (chessman, sym);

}

fscanf (input," %s" ,&sym);

}

}

}

}

fclose (input);

}

//что в данной клетке

int occupied_space (int K1, int K2, work ell)

{

for (int i = 0; i <= ell. n; i++){

if (ell.table[i]. x == K1 && ell. table[i]. y == K2)

return ell. table[i]. chessmanNo;

}

return -1;

}

//пешка рядом

int pawn_of_king (int x, int y, int flg, work elem)

{

const int s = x, c = y;

int M = -3, N = -3;

//белые

if (flg == 1) (7 < N && N < 16))

return 0;

//не одна из пешек не претендует на это место

return 1;

//чёрные

else{

if ((s-1 >= 0 && s-1 <= 7)&&(c+1 >= 0 && c+1 <= 7))

M = occupied_space (s-1, c+1, elem);

if ((s+1 >= 0 && s+1 <= 7)&&(c+1 >= 0 && c+1 <= 7))

N = occupied_space (s+1, c+1, elem);

//важный ход пешки

if ((23 < M && M < 32) && (23 < N && N < 32))

return 0;

//не одна из пешек не претендует на это место

return 1;

}

}

//конь рядом

int kNight_of_king (int x, int y, int flg, work elem)

{

const int s = x, c = y;

int M = -3, N = M, V = M, K = M, G = M, Q = M, P = M, D = M;

//если фигура входит в границы

if ((s+2 >= 0 && s+2 <= 7)&&(c+1 >= 0 && c+1 <= 7))

M = occupied_space (s+2, c+1, elem);

//если фигура входит в границы

if ((s+2 >= 0 && s+2 <= 7)&&(c-1 >= 0 && c-1 <= 7))

N = occupied_space (s+2, c-1, elem);

//если фигура входит в границы

if ((s-2 >= 0 && s-2 <= 7)&&(c+1 >= 0 && c+1 <= 7))

V = occupied_space (s-2, c+1, elem);

//если фигура входит в границы

if ((s-2 >= 0 && s-2 <= 7)&&(c-1 >= 0 && c-1 <= 7))

K = occupied_space (s-2, c-1, elem);

//если фигура входит в границы

if ((s-1 >= 0 && s-1 <= 7)&&(c-2 >= 0 && c-2 <= 7))

G = occupied_space (s-1, c-2, elem);

//если фигура входит в границы

if ((s+1 >= 0 && s+1 <= 7)&&(c-2 >= 0 && c-2 <= 7))

Q = occupied_space (s+1, c-2, elem);

//если фигура входит в границы

if ((s-1 >= 0 && s-1 <= 7)&&(c+2 >= 0 && c+2 <= 7))

P = occupied_space (s-1, c+2, elem);

//если фигура входит в границы

if ((s+1 >= 0 && s+1 <= 7)&&(c+2 >= 0 && c+2 <= 7))

D = occupied_space (s+1, c+2, elem);

//определение цвета фигур

if (flg == 1)

elseQ == 17

}

//слон рядом

int bishop_of_king (int x, int y, int flg, work elem)

{

int M = -1, g1, g2, g3, g4;

const int s = x, c = y;

//цвет

if (flg == 1){

g1 = 2;

g2 = 4;

g3 = 5;

g4 = 20;

}

else{

g1 = 18;

g2 = 19;

g3 = 21;

g4 = 3;

}

//пока фигура входит в границы или является сама королём

do{

x++;

y++;

if ((x <= 7 && x >= 0)&&(y <= 7 && y >= 0))M == g3)

return 0;

}while ((M == -1|| M == g4) && (x <= 7 && x >= 0)&&(y <= 7 && y >= 0));

x = s, y =c;

//пока фигура входит в границы или является сама королём

do{

x++;

y—;

if ((x <= 7 && x >= 0)&&(y <= 7 && y >= 0))M == g2

}while ((M == -1|| M == g4) && (x <= 7 && x >= 0)&&(y <= 7 && y >= 0));

x = s, y =c;

//пока фигура входит в границы или является сама королём

do{

x—;

y—;

if ((x <= 7 && x >= 0)&&(y <= 7 && y >= 0))

M = occupied_space (x, y, elem);

if (M == g1

}while ((M == -1|| M == g4) && (x <= 7 && x >= 0)&&(y <= 7 && y >= 0));

x = s, y =c;

//пока фигура входит в границы или является сама королём

do{

x—;

y++;

if ((x <= 7 && x >= 0)&&(y <= 7 && y >= 0))

M = occupied_space (x, y, elem);

if (M == g1

}while ((M == -1|| M == g4) && (x <= 7 && x >= 0)&&(y <= 7 && y >= 0));

return 1;

}

//лодья рядом

int rook_of_king (int x, int y, int flg, work elem)

{

int M = -1, g1, g2, g3, g4;

const int s = x, c = y;

if (flg == 1){

g1 = 0;

g2 = 4;

g3 = 7;

g4 = 20;

}

else{

g1 = 16;

g2 = 19;

g3 = 23;

g4 = 3;

}

//пока фигура входит в границы или является сама королём

do{

x++;

if (x <= 7 && x >= 0) M == g2

}while ((M == -1|| M == g4) && (x <= 7 && x >= 0));

x = s, y = c;

//пока фигура входит в границы или является сама королём

do{

x—;

if (x <= 7 && x >= 0)

M = occupied_space (x, y, elem);

if (M == g1

}while ((M == -1|| M == g4) && (x <= 7 && x >= 0));

x = s, y = c;

//пока фигура входит в границы или является сама королём

do{

y—;

if (y <= 7 && y >= 0) M == g3)

return 0;

}while ((M == -1|| M == g4) && (y <= 7 && y >= 0));

y = c;

//пока фигура входит в границы или является сама королём

do{

y++;

if (y <= 7 && y >= 0)

}while ((M == -1|| M == g4) && (y <= 7 && y >= 0));

return 1;

}

//король рядом

int king_of_king (int x, int y, int flg, work elem)

{

int g, M;

const int a = x, b = y;

if (flg == 1)

g = 3;

else

g = 20;

//если фигура входит в границы

if ((a+1 >= 0 && a+1 <= 7)&&(b+1 >= 0 && b+1 <= 7)){

M = occupied_space (a+1, b+1, elem);

if (M == g)

return 0;

}

//если фигура входит в границы

if ((a-1 >= 0 && a-1 <= 7)&&(b-1 >= 0 && b-1 <= 7)){

M = occupied_space (a-1, b-1, elem);

if (M == g)

return 0;

}

//если фигура входит в границы

if ((a+1 >= 0 && a+1 <= 7)&&(b-1 >= 0 && b-1 <= 7)){

M = occupied_space (a+1, b-1, elem);

if (M == g)

return 0;

}

//если фигура входит в границы

if ((a-1 >= 0 && a-1 <= 7)&&(b+1 >= 0 && b+1 <= 7)){

M = occupied_space (a-1, b+1, elem);

if (M == g)

return 0;

}

//если фигура входит в границы

if (a-1 >= 0 && a-1 <= 7){

M = occupied_space (a-1, b, elem);

if (M == g)

return 0;

}

//если фигура входит в границы

if (a+1 >= 0 && a+1 <= 7){

M = occupied_space (a+1, b, elem);

if (M == g)

return 0;

}

//если фигура входит в границы

if (b+1 >= 0 && b+1 <= 7){

M = occupied_space (a, b+1, elem);

if (M == g)

return 0;

}

//если фигура входит в границы

if (b-1 >= 0 && b-1 <= 7){

M = occupied_space (a, b-1, elem);

if (M == g)

return 0;

}

return 1;

}

//связывающая подпрограмма для короля

int communication_king (int k, int c, int f, work el){

if (king_of_king (k, c, f, el)){

if (pawn_of_king (k, c, f, el)){

if (rook_of_king (k, c, f, el)){

if (bishop_of_king (k, c, f, el)){

if (kNight_of_king (k, c, f, el))

return 1;

}

}

}

}

return 0;

}

//король

void king (stack **B, int a, int c, int f, work ell)

{

const int a1 = a, b1 = c;

int W₁ = 16, B₁ = 0, g1, g2, M;

//цвет

if (f == 1){

g1 = B₁;

g2 = B₁ + 15;

}

else{

g1 = W₁;

g2 = W₁ + 15;

}

//просмотр всех вариантов хода королём

//если фигура входит в границы

if ((a1+1 >= 0 && a1+1 <= 7)&&(b1+1 >= 0 && b1+1 <= 7)){

//не одна из фигур не претендует на клетку

if (communication_king (a1+1, b1+1, f, ell)) M == -1)

in_stack (&(*B), a1+1, b1+1);

}

//если фигура входит в границы

if ((a1−1 >= 0 && a1−1 <= 7)&&(b1−1 >= 0 && b1−1 <= 7)){

//не одна из фигур не претендует на клетку

if (communication_king (a1−1, b1−1, f, ell))

M = occupied_space (a1−1, b1−1, ell);

if ((M >= g1 && M <= g2)

}

//если фигура входит в границы

if ((a1+1 >= 0 && a1+1 <= 7)&&(b1−1 >= 0 && b1−1 <= 7)){

//не одна из фигур не претендует на клетку

if (communication_king (a1+1, b1−1, f, ell))

M = occupied_space (a1+1, b1−1, ell);

if ((M >= g1 && M <= g2)

}

//если фигура входит в границы

if ((a1−1 >= 0 && a1−1 <= 7)&&(b1+1 >= 0 && b1+1 <= 7)){

//не одна из фигур не претендует на клетку

if (communication_king (a1−1, b1+1, f, ell)) M == -1)

in_stack (&(*B), a1−1, b1+1);

}

//если фигура входит в границы

if (a1−1 >= 0 && a1−1 <= 7){

//не одна из фигур не претендует на клетку

if (communication_king (a1−1, b1, f, ell))

}

//если фигура входит в границы

if (a1+1 >= 0 && a1+1 <= 7){

//не одна из фигур не претендует на клетку

if (communication_king (a1+1, b1, f, ell))

}

//если фигура входит в границы

if (b1+1 >= 0 && b1+1 <= 7){

//не одна из фигур не претендует на клетку

if (communication_king (a1, b1+1, f, ell))

M = occupied_space (a1, b1+1, ell);

if ((M >= g1 && M <= g2)

}

//если фигура входит в границы

if (b1−1 >= 0 && b1−1 <= 7){

//не одна из фигур не претендует на клетку

if (communication_king (a1, b1−1, f, ell))

}

}

//ферзь

void queen (stack **B, int a, int c, int f, work ell)

{

bishop (&(*B), a, c, f, ell);

rook (&(*B), a, c, f, ell);

}

//слон

void bishop (stack **B, int a, int c, int f, work ell)

{

const int a1 = a, b1 = c;

int W₁ = 16, B₁ = 0, g1, g2, g3, M;

//цвет

if (f == 1){

g1 = B₁;

g2 = B₁ + 15;

g3 = 3;

}

else{

g1 = W₁;

g2 = W₁ + 15;

g3 = 20;

}

//просмотр всех вариантов хода слоном

//до тех пор пока не встретится король противника или очередная клетка будет занята

do M == -1) && M ≠ g3)

in_stack (&(*B), a, c);

while ((M == -1)&&((a >= 0 && a <= 7)&&(c >= 0 && c <= 7)) && M ≠ g3);

a = a1, c = b1;

//до тех пор пока не встретится король противника или очередная клетка будет занята

dowhile ((M == -1)&&((a >= 0 && a <= 7)&&(c >= 0 && c <= 7)) && M ≠ g3);

a = a1, c = b1;

//до тех пор пока не встретится король противника или очередная клетка будет занята

do M == -1) && M ≠ g3)

in_stack (&(*B), a, c);

while ((M == -1)&&((a >= 0 && a <= 7)&&(c >= 0 && c <= 7)) && M ≠ g3);

a = a1, c = b1;

//до тех пор пока не встретится король противника или очередная клетка будет занята

dowhile ((M == -1)&&((a >= 0 && a <= 7)&&(c >= 0 && c <= 7)) && M ≠ g3);

}

//лодья

void rook (stack **B, int a, int c, int f, work ell)

{

const int a1 = a, b1 = c, z1 = -1, z2 = 8;

int W₁ = 16, B₁ = 0, g1, g2, g3, M;

//цвет

if (f == 1){

g1 = B₁;

g2 = B₁ + 15;

g3 = 3;

}

else{

g1 = W₁;

g2 = W₁ + 15;

g3 = 20;

}

//просмотр всех вариантов хода ладьёй

//до тех пор пока не встретится король противника или очередная клетка будет занята

dowhile ((M == -1) && ((a > z1) && (a < z2)) && M ≠ g3);

a = a1, c = b1;

//до тех пор пока не встретится король противника или очередная клетка будет занята

do M == -1) && M ≠ g3)

in_stack (&(*B), a, c);

while ((M == -1) && ((a > z1) && (a < z2)) && M ≠ g3);

a = a1, c = b1;

//до тех пор пока не встретится король противника или очередная клетка будет занята

do

c—;

M = occupied_space (a, c, ell);

if ((c > z1 && c < z2) && ((M >= g1 && M <= g2) while ((M == -1) && ((c > z1) && (c < z2)) && M ≠ g3);

a = a1, c = b1;

//до тех пор пока не встретится король противника или очередная клетка будет занята

do

c++;

M = occupied_space (a, c, ell);

if (((c > z1) && (c < z2)) && ((M >= g1 && M <= g2) while ((M == -1) && ((c > z1) && (c < z2)) && M ≠ g3);

}

//конь

void kNight (stack **B, int a, int c, int f, work ell)

{

const int a1 = a, b1 = c;

int W₁ = 16, B₁ = 0, g1, g2, g3, M;

//цвет

if (f == 1){

g1 = B₁;

g2 = B₁ + 15;

g3 = 3;

}

else{

g1 = W₁;

g2 = W₁ + 15;

g3 = 20;

}

//просмотр всех вариантов хода конём

M = occupied_space (a1+2,b1−1,ell);

//если координата в границах доски фигура в клетке цвета противника и не король

if (((a1+2 >= 0 && a1+2 <= 7)&&(b1−1 >= 0 && b1−1 <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M ≠ g3)

in_stack (&(*B), a1+2, b1−1);

M = occupied_space (a1+2,b1+1,ell);

//если координата в границах доски фигура в клетке цвета противника и не король

if (((a1+2 >= 0 && a1+2 <= 7)&&(b1+1 >= 0 && b1+1 <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M ≠ g3)

in_stack (&(*B), a1+2, b1+1);

M = occupied_space (a1−2,b1+1,ell);

//если координата в границах доски фигура в клетке цвета противника и не король

if (((a1−2 >= 0 && a1−2 <= 7)&&(b1+1 >= 0 && b1+1 <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M ≠ g3)

in_stack (&(*B), a1−2, b1+1);

M = occupied_space (a1−2,b1−1,ell);

//если координата в границах доски фигура в клетке цвета противника и не король

if (((a1−2 >= 0 && a1−2 <= 7)&&(b1−1 >= 0 && b1−1 <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M ≠ g3)

in_stack (&(*B), a1−2, b1−1);

M = occupied_space (a1−1,b1−2,ell);

//если координата в границах доски фигура в клетке цвета противника и не король

if (((a1−1 >= 0 && a1−1 <= 7)&&(b1−2 >= 0 && b1−2 <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M ≠ g3)

in_stack (&(*B), a1−1, b1−2);

M = occupied_space (a1+1,b1−2,ell);

//если координата в границах доски фигура в клетке цвета противника и не король

if (((a1+1 >= 0 && a1+1 <= 7)&&(b1−2 >= 0 && b1−2 <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M ≠ g3)

in_stack (&(*B), a1+1, b1−2);

M = occupied_space (a1−1,b1+2,ell);

//если координата в границах доски фигура в клетке цвета противника и не король

if (((a1−1 >= 0 && a1−1 <= 7)&&(b1+2 >= 0 && b1+2 <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M ≠ g3)

in_stack (&(*B), a1−1, b1+2);

M = occupied_space (a1+1,b1+2,ell);

//если координата в границах доски фикура в клетке цвета противника и не король

if (((a1+1 >= 0 && a1+1 <= 7)&&(b1+2 >= 0 && b1+2 <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M ≠ g3)

in_stack (&(*B), a1+1, b1+2);

}

//пешка

void pawn (stack **B, int a, int c, int f, work ell)

{

const int a1 = a, b1 = c;

int W₁ = 16, B₁ = 0, g1, g2, g3, M;

//цвет

if (f == 1){

g1 = B₁;

g2 = B₁ + 15;

g3 = 3;

if (c == 6){

//одна вперёд

M = occupied_space (a1,b1−1,ell);

if ((b1−1 >= 0 && b1−1 <= 7) && (M == -1)){

in_stack (&(*B), a1, b1−1);

//две вперёд

M = occupied_space (a1,b1−2,ell);

if ((b1−2 >= 0 && b1−2 <= 7) && (M == -1))

in_stack (&(*B), a1, b1−2);

}

//одна влево

M = occupied_space (a1−1,b1−1,ell);

if ((a1−1 >= 0 && a1−1 <= 7) && (b1−1 >= 0 && b1−1 <= 7) && (M >= g1 && M <= g2) && M ≠ g3)

in_stack (&(*B), a1−1, b1−1);

//одна вправо

M = occupied_space (a1+1,b1−1,ell);

if ((a1+1 >= 0 && a1+1 <= 7) && (b1−1 >= 0 && b1−1 <= 7) && (M >= g1 && M <= g2) && M ≠ g3)

in_stack (&(*B), a1+1, b1−1);

}

else{

//одна вперёд

M = occupied_space (a1,b1−1,ell);

if ((b1−1 >= 0 && b1−1 <= 7) && (M == -1))

in_stack (&(*B), a1, b1−1);

//одна влево

M = occupied_space (a1−1,b1−1,ell);

if ((a1−1 >= 0 && a1−1 <= 7) && (b1−1 >= 0 && b1−1 <= 7) && (M >= g1 && M <= g2) && M ≠ g3)

in_stack (&(*B), a1−1, b1−1);

//одна вправо

M = occupied_space (a1+1,b1−1,ell);

if ((a1+1 >= 0 && a1+1 <= 7) && (b1−1 >= 0 && b1−1 <= 7) && (M >= g1 && M <= g2) && M ≠ g3)

in_stack (&(*B), a1+1, b1−1);

}

}

else{

g1 = W₁;

g2 = W₁ + 15;

g3 = 20;

if (c == 1){

//одна вперёд

M = occupied_space (a1,b1+1,ell);

if ((b1+1 >= 0 && b1+1 <= 7) && (M == -1)){

in_stack (&(*B), a1, b1+1);

//две вперёд

M = occupied_space (a1,b1+2,ell);

if ((b1+2 >= 0 && b1+2 <= 7) && (M == -1))

in_stack (&(*B), a1, b1+2);

}

//одна влево

M = occupied_space (a1−1,b1+1,ell);

if ((a1−1 >= 0 && a1−1 <= 7) && (b1+1 >= 0 && b1+1 <= 7) && (M >= g1 && M <= g2) && M ≠ g3)

in_stack (&(*B), a1−1, b1+1);

//одна вправо

M = occupied_space (a1+1,b1+1,ell);

if ((a1+1 >= 0 && a1+1 <= 7) && (b1+1 >= 0 && b1+1 <= 7) && (M >= g1 && M <= g2) && M ≠ g3)

in_stack (&(*B), a1+1, b1+1);

}

else{

//одна вперёд

M = occupied_space (a1,b1+1,ell);

if ((b1+1 >= 0 && b1+1 <= 7) && (M == -1))

in_stack (&(*B), a1, b1+1);

//одна влево

M = occupied_space (a1−1,b1+1,ell);

if ((a1−1 >= 0 && a1−1 <= 7) && (b1+1 >= 0 && b1+1 <= 7) && (M >= g1 && M <= g2) && M ≠ g3)

in_stack (&(*B), a1−1, b1+1);

//одна вправо

M = occupied_space (a1+1,b1+1,ell);

if ((a1+1 >= 0 && a1+1 <= 7) && (b1+1 >= 0 && b1+1 <= 7) && (M >= g1 && M <= g2) && M ≠ g3)

in_stack (&(*B), a1+1, b1+1);

}

}

}

//копирование стека

void copying (stack *Q1, stack **Q2)

{

while (Q1 ≠ NULL) {

if (*Q2 == NULL){

*Q2 = new stack;

(*Q2)->X = Q1->X;

(*Q2)->Y = Q1->Y;

(*Q2)->next = NULL;

}

else{

stack *R = new stack;

R->X = Q1->X;

R->Y = Q1->Y;

R->next = (*Q2);

(*Q2) = R;

}

Q1 = Q1->next;

}

}

//в стек

void in_stack (stack **Q, int x₁, int y₁)

{

if (*Q == NULL){

*Q = new stack;

(*Q)->X = x₁;

(*Q)->Y = y₁;

(*Q)->next = NULL;

}

else{

stack *R = new stack;

R->X = x₁;

R->Y = y₁;

R->next = *Q;

*Q = R;

}

}

//из стека

int out_stack (stack**Q, int *x₁, int *y₁)

{

if (*Q == NULL)

return 0;

*x₁ = (*Q)->X;

*y₁ = (*Q)->Y;

stack *N = *Q;

*Q = (*Q)->next;

delete N;

return 1;

}

//поиск в стеке

int search_stack (stack*Q, int n, int m)

{

while (Q ≠ NULL){

if (Q->X == n && Q->Y == m)

return 1;

Q = Q->next;

}

return 0;

}

/*Form1.h*/

#pragma once

#include

#include

#include «chessman.h»

extern FILE *fl, *fll, *fll2, *input;

int C, old_X, old_Y;// фигура для пп clik

namespace chess {

using namespace System;

using namespace System: ComponentModel;

using namespace System: Collections;

using namespace System: Windows:Forms;

using namespace System: Data;

using namespace System: Drawing;

/// Сводка для Form1

int fig[63];

public ref class Form1: public System: Windows:Forms:Form

{

public:

//необходимая информация о фигурх

void input_fl (color₁ *B, color₂ *W)

{

int k = 0, q = 0;

char ch[4];

if ((fl = fopen («fl.txt», «r»)) == NULL)

perror («error»);

else{

fscanf (fl," %s" ,&B->chessBlack);

fscanf (fl," %s" ,&W->chessWhite);

while ((k < 16) && fscanf (fl," %s" ,&ch))

{

strcpy (B->Bcolor[k]. chessman, ch);

B->Bcolor[k]. No = k;

k++;

}

while (fscanf (fl," %s" ,&ch) ≠ EOF)

{

strcpy (W->Wcolor[q]. chessman, ch);

W->Wcolor[q]. No = k;

q++;

k++;

}

}

fclose (fl);

}

//инициализация фигур

void initchess ()

{

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

fig[i]= -5;

initznak ();

}

void initznak ()

{

for (int i = 32; i < 63; i++)

fig[i]= -5;

}

//место фигуры iфигура, y, x — место (они с -1)

void figchess (int i, int y, int x)

{

fig[i] = y*8+x;

}

//считаные нажатием координаты

void clik (int a, int b, stack **course)

{

//инициализация символов хода

initznak ();

work ell;

stack *backup = NULL;

int flg = 0;

//вспомогательные элементы

closefile (&ell);

closefil_stakc (&backup);

//выбор фигуры

if (backup == NULL)

C == 21))

bishop (&(*course), a, b, flg, ell);

//лодья

if ((C == 0

//выбор места переноса фигуры

else

{

int U, d = 0, h = 0;

//необходимо чтобы выбранное место соответствовало правильному ходу

if (search_stack (backup, a, b)){

U = occupied_space (old_X, old_Y, ell);

while (ell.table[d]. chessmanNo ≠ U){

d++;

}

U = occupied_space (a, b, ell);

//место пусто переместить

if (U == -1){

ell.table[d]. x = a;

ell.table[d]. y = b;

}

//место занято срубить

else{

while (ell.table[h]. chessmanNo ≠ U)

h++;

ell.table[h]. x = -5;

ell.table[h]. y = -5;

ell.table[d]. x = a;

ell.table[d]. y = b;

}

//смена изображения

initznak ();

for (int j = 0; j < ell. n; j++)

figchess (ell.table[j]. chessmanNo, ell. table[j].y, ell. table[j].x);

}

//вспомогательные элементы

while (out_stack (&backup, &old_X, &old_Y))

old_X = 0, old_Y = 0;

openfile_stakc (&backup);

openfile (ell);

}

}

//основной алгоритм

void myalg ()

{

color₁ Bl;

color₂ Wh;

work elem;

input_fl (&Bl,&Wh);

myscanf (Bl, Wh, &elem);

openfile (elem);

for (int j = 0; j < elem. n; j++)

//выполнение вывода пользовательской расстановки фигур

figchess (elem.table[j]. chessmanNo, elem. table[j]. y, elem. table[j]. x);

}

Form1(void)

{

initchess ();

InitializeComponent ();

myalg ();

}

protected:

~Form1()

{

if (components)

{

delete components;

}

}

private: System: Windows:Forms:PictureBox^ pictureBox1;

protected:

private:

System:ComponentModel:Container ^components;

#pragma region Windows Form Designer generated code

void InitializeComponent (void)

{

this->pictureBox1 = (gcnew System: Windows:Forms:PictureBox ());

(cli:safe_cast (this->pictureBox1))->BeginInit ();

this->SuspendLayout ();

// pictureBox1

this->pictureBox1->BackColor = System: Drawing:Color:White;

this->pictureBox1->Location = System: Drawing:Point (12, 12);

this->pictureBox1->Name = L" pictureBox1″ ;

this->pictureBox1->Size = System: Drawing:Size (400, 400);

this->pictureBox1->TabIndex = 0;

this->pictureBox1->TabStop = false;

this->pictureBox1->Paint += gcnew System: Windows:Forms:PaintEventHandler (this, &Form1:pictureBox1_Paint);

this->pictureBox1->MouseClick += gcnew System: Windows:Forms:MouseEventHandler (this,&Form1:pictureBox1_MouseClick);

// Form1

this->AutoScaleDimensions = System: Drawing:SizeF (6, 13);

this->AutoScaleMode = System: Windows:Forms:AutoScaleMode:Font;

this->ClientSize = System: Drawing:Size (424, 420);

this->Controls->Add (this->pictureBox1);

this->FormBorderStyle = System: Windows:Forms:FormBorderStyle:FixedSingle;

this->MaximizeBox = false;

this->Name = L" Form1″ ;

this->Text = L" Form1″ ;

(cli:safe_cast (this->pictureBox1))->EndInit ();

this->ResumeLayout (false);

}

#pragma endregion

private: System: Void pictureBox1_Paint (System:Object^ sender, System: Windows:Forms:PaintEventArgs^ e) {

Graphics^ g = e->Graphics;

int n = 0;

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

{

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

{

if (n % 2 == 1)

g->FillRectangle (Brushes:Brown, j * 50, i * 50, 50, 50);

else

g->FillRectangle (Brushes:Wheat, j * 50, i * 50, 50, 50);

n++;

}

n++;

}

System:Drawing:Font^ drawFont = gcnew System: Drawing:Font («Arial», 29);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[0] % 8 * 50, fig[0] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[1] % 8 * 50, fig[1] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[2] % 8 * 50, fig[2] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[3] % 8 * 50, fig[3] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[4] % 8 * 50, fig[4] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[5] % 8 * 50, fig[5] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[6] % 8 * 50, fig[6] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[7] % 8 * 50, fig[7] / 8 * 50);

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

g->DrawString (L" ?", drawFont, Brushes: Black, fig[8 + i] % 8 * 50, fig[8 + i] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[16] % 8 * 50, fig[16] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[17] % 8 * 50, fig[17] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[18] % 8 * 50, fig[18] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[19] % 8 * 50, fig[19] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[20] % 8 * 50, fig[20] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[21] % 8 * 50, fig[21] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[22] % 8 * 50, fig[22] / 8 * 50);

g->DrawString (L" ?", drawFont, Brushes: Black, fig[23] % 8 * 50, fig[23] / 8 * 50);

for (int i = 24; i < 32; i++)

g->DrawString (L" ?", drawFont, Brushes: Black, fig[i] % 8 * 50, fig[ i] / 8 * 50);

for (int i = 32; i < 63; i++)

g->DrawString (L" ?", drawFont, Brushes: Blue, fig[i] % 8 * 50, fig[i] / 8 * 50);

}

private: System: Void pictureBox1_MouseClick (System:Object^ sender, System: Windows:Forms:MouseEventArgs^ e) {

stack *poss_course = NULL;

int x1 = e->X / 50, y1 = e->Y / 50;

clik (x1, y1, &poss_course);

if (poss_course ≠ NULL){

for (int s = 0, k = 0, z = 32; out_stack (&poss_course, &s, &k); z++)

figchess (z, k, s);

}

pictureBox1->Refresh ();

}

};

}

/*main.cpp*/

// chess. cpp: главный файл проекта.

#include «stdafx.h»

#include «Form1.h»

#include «chessman.h»

using namespace chess;

[STAThreadAttribute]

int main (array ^args)

{

// Включение визуальных эффектов Windows XP до создания каких-либо элементов управления

Application:EnableVisualStyles ();

Application:SetCompatibleTextRenderingDefault (false);

// Создание главного окна и его запуск

Application:Run (gcnew Form1());

return 0;

}

/*chessman.cpp*/

#ifndef CHESSMAN_H

#define CHESSMAN_H

//Таблица с чёрными фигурами

struct Black {

char chessman [4];

int No;

};

struct color₁ {

Black Bcolor [16];

char chessBlack [8];

};

//Таблица с белыми фигурами

struct White {

char chessman [4];

int No;

};

struct color₂ {

White Wcolor [16];

char chessWhite [7];

};

//Рабочая таблица

struct elem {

int chessmanNo;

int x;

int y;

};

struct work {

elem table [33];

int n;

};

struct stack {

stack *next;

int X;

int Y;

};

void myscanf (color₁ B, color₂ W, work *el);

//королль

void king (stack **B, int a, int c, int f, work ell);

//ферзь

void queen (stack **B, int a, int c, int f, work ell);

//слон

void bishop (stack **B, int a, int c, int f, work ell);

//лодья

void rook (stack **B, int a, int c, int f, work ell);

//конь

void kNight (stack **B, int a, int c, int f, work ell);

//пешка

void pawn (stack **B, int a, int c, int f, work ell);

//копирование стека

void copying (stack *Q1, stack **Q2);

//в стек

void in_stack (stack **Q, int x, int y);

//из стека

int out_stack (stack**Q, int *x, int *y);

//что в данной клетке

int occupied_space (int K1, int K2, work ell);

void openfile (work ell);

void closefile (work *ell);

void openfile_stakc (stack **B);

void closefil_stakc (stack **B);

int search_stack (stack*Q, int n, int m);

#endif

7. Набор тестов

8. Результаты работы программы

1. Хиценко В. П., Шапошникова Т. А. Структуры данных и алгоритмы: методические указания. Новосибирск: НГТУ, 2008.