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

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

Министерство образования и наук Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

Курсовая работа

по практикуму на ЭВМ: Структуры данных и алгоритмы

Факультет

прикладной математики и информатики

Группа ПМИ-22

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

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

Новосибирск

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

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

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

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

C = (B, W)         

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

= (N, Fj, Ki) ∪ {∅ }

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

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

= (Xi, Yj) Ki - координата шахматной фигуры i = 1, 64∈ {‘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

= (Xi, Yj) Ki - координата шахматной фигуры i = 1, 64∈ {‘a’, …, ‘h’} i = 1, 8 координата по x

Yj ∈ {‘1’, …, ‘8’} j = 1, 8  координата по y

2.2 Результат

D = (T, n) ∪ {∅ }

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

T = {ti | ti =(Ns, Xj, Yi) i = 1,32}

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

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-х элементов отделённых друг от друга запятыми и пробелами

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

elem

{chessmanNo;x;y;

}work

{table [32];n;

}

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

{= 0;(выбор фигуры)

{(белые)= 1;(королль)

//возможные ходы(a, b, flg);(ферзь)

//возможные ходы(a, b, flg);(слон)

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

bishop(a, b, flg);(ладья)

//возможные ходы(a, b, flg);(конь)

//возможные ходы(a, b, flg);(пешка)

//возможные ходы(a, b, flg);

}

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

{

if(место занято)

срубить фигуру;

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

}

}

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

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

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

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

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

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

5.1 Модуль 1

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

назначение:

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

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

5.2 Модуль 2

процедура input_fl

назначение:

ввод из файла обозначения фигур привычных пользователю

инициализация структур: color_1, color_2

прототип: void input_fl(color_1 *B, color_2 *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_1, color_2 (структуры содержащие обозначение фигур удобных пользователю и их соответствующее обозначения в программе),(таблица содержащая результат), stack (стек для хранения возможных ходов)

содержит объявление процедур: myscanf, king, queen, bishop, rook, kNight, pawn, in_stack

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

5.4 Модуль 4

функция searchBlack

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

- прототип: searchBlack(char *s, color_1 B)

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

данная функция возвращает номер под которые данная фигура известна программе

функция searchWhite

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

- прототип: int searchWhite(char *s, color_2 W)

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

данная функция возвращает номер под которыми данная фигура известна программе

процедура myscanf

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

- прототип: void myscanf(color_1 B, color_2 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_1, int y_1)

функция out_stack

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

-прототип: int out_stack(stack**Q, int *x_1, int *y_1)

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

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

/*chessman.h*/

#include "StdAfx.h"

#include<string.h>

#include <stdio.h>

#include<locale.h>

#include "chessman.h"*fl, *fll, *fll2, *input;

//Координаты по xx [] = "abcdefgh";

//Координаты по yy [] = "87654321";

void openfile(work ell)

{((fll = fopen("fll.txt", "w")) == NULL)("error");{(int i = 0; i<= ell.n; i++){(fll,"%d ",ell.table[i].chessmanNo);(fll,"%d ",ell.table[i].x);(fll,"%d ",ell.table[i].y);

}(fll);

}

}closefile(work *ell)

{((fll = fopen("fll.txt", "r")) == NULL)("error");{(int i = 0; fscanf(fll,"%d ",&(ell->table[i].chessmanNo)) != EOF; i++){(fll,"%d ",&(ell->table[i].x));(fll,"%d ",&(ell->table[i].y));>n = i;

}(fll);

}

}openfile_stakc(stack **B)

{((fll2 = fopen("fll2.txt", "w")) == NULL)("error");{f, v;(out_stack(&(*B), &f, &v)){(fll,"%d ",f);(fll,"%d\n",v);

}(fll2);

}

}closefil_stakc(stack **B)

{((fll2 = fopen("fll2.txt", "r")) == NULL)("error");{p, r;(fscanf(fll2,"%d ",&p) != EOF){(fll,"%d ",&r);_stack(&(*B), p, r);

}(fll2);

}

}

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

int searchBlack(char *s, color_1 B)

{(int k = 0; k<16; k++){(!strcmp(B.Bcolor[k].chessman,s))B.Bcolor[k].No;

}-1;

}

//поиск по белым фигурамsearchWhite(char *s, color_2 W)

{(int k = 0; k<16; k++){(!strcmp(W.Wcolor[k].chessman,s))W.Wcolor[k].No;

}-1;

}

//считывание обозначение пользователяmyscanf(color_1 B, color_2 W, work *el)

{((input = fopen("input.txt", "r")) == NULL)("error");{wrk, i;>n = 0;sym[5],chessm[3],chessman[3], slovo[8], same = '0', sign[] = ";";

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

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

{

//чёрные фигуры(strcmp(B.chessBlack, slovo) == 0)

{

//считываем до ;(input,"%s",&sym);

while(sym[0] != sign[0])

{

// координата(sym[1] >= '0' && sym[1] <= '9')

{

//если одинаковые фигуры(same != '0')

{(chessm,chessman);(chessm,&same);= searchBlack(chessm, B);>table[el->n].chessmanNo = wrk;

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

while(sym[0] != x[i])++;>table[el->n].x = i;

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

while(sym[1] != y[i])++;>table[el->n].y = i;

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

}

{

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

i = 0;(sym[0] != x[i])++;>table[el->n].x = i;

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

while(sym[1] != y[i])++;>table[el->n].y = i;

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

same++;

}

}

//фигура

{= searchBlack(sym, B);>table[el->n].chessmanNo = wrk;= '0';(chessman,sym);

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

}

}

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

{

//считываем до ;(input,"%s",&sym);(sym[0] != sign[0])

{

// координата(sym[1] >= '0' && sym[1] <= '9')

{

//если одинаковые фигуры(same != '0')

{(chessm,chessman);(chessm,&same);= searchWhite(chessm, W);>table[el->n].chessmanNo = wrk;

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

while(sym[0] != x[i])++;>table[el->n].x = i;

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

while(sym[1] != y[i])++;>table[el->n].y = i;

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

}

{

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

i = 0;(sym[0] != x[i])++;>table[el->n].x = i;

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

while(sym[1] != y[i])++;>table[el->n].y = i;

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

same++;

}

}

//фигура

{= searchWhite(sym, W);>table[el->n].chessmanNo = wrk;= '0';(chessman,sym);

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

}

}

}

}(input);

}

//что в данной клеткеoccupied_space(int K1, int K2, work ell)

{(int i = 0; i <= ell.n; i++){(ell.table[i].x == K1 && ell.table[i].y == K2)ell.table[i].chessmanNo;

}-1;

}

//пешка рядомpawn_of_king(int x, int y, int flg, work elem)

{int s = x, c = y;M = -3, N = -3;

//белые(flg == 1){((s-1 >= 0 && s-1 <= 7)&&(c-1 >= 0 && c-1 <= 7))= occupied_space(s-1, c-1, elem);((s+1 >= 0 && s+1 <= 7)&&(c-1 >= 0 && c-1 <= 7))= occupied_space(s+1, c-1, elem);

//важный ход пешки((7 < M && M < 16) || (7 < N && N < 16))0;

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

return 1;

}

//чёрные{((s-1 >= 0 && s-1 <= 7)&&(c+1 >= 0 && c+1 <= 7))= occupied_space(s-1, c+1, elem);((s+1 >= 0 && s+1 <= 7)&&(c+1 >= 0 && c+1 <= 7))= occupied_space(s+1, c+1, elem);

//важный ход пешки((23 < M && M < 32) && (23 < N && N < 32))0;

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

return 1;

}

}

//конь рядомkNight_of_king(int x, int y, int flg, work elem)

{int s = x, c = y;M = -3, N = M, V = M, K = M, G = M, Q = M, P = M, D = M;

//если фигура входит в границы((s+2 >= 0 && s+2 <= 7)&&(c+1 >= 0 && c+1 <= 7))

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

//если фигура входит в границы((s+2 >= 0 && s+2 <= 7)&&(c-1 >= 0 && c-1 <= 7))

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

//если фигура входит в границы((s-2 >= 0 && s-2 <= 7)&&(c+1 >= 0 && c+1 <= 7))

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

//если фигура входит в границы((s-2 >= 0 && s-2 <= 7)&&(c-1 >= 0 && c-1 <= 7))

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

//если фигура входит в границы((s-1 >= 0 && s-1 <= 7)&&(c-2 >= 0 && c-2 <= 7))

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

//если фигура входит в границы((s+1 >= 0 && s+1 <= 7)&&(c-2 >= 0 && c-2 <= 7))

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

//если фигура входит в границы((s-1 >= 0 && s-1 <= 7)&&(c+2 >= 0 && c+2 <= 7))

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

//если фигура входит в границы((s+1 >= 0 && s+1 <= 7)&&(c+2 >= 0 && c+2 <= 7))

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

//определение цвета фигур(flg == 1){(M == 1||M == 6||N == 1||N == 6||V == 1||V == 6||K == 1||K == 6)

return 0;(G == 1||G == 6||Q == 1||Q == 6||P == 1||P == 6||D == 1||D == 6)0;1;

}{(M == 17||M == 22||N == 17||N == 22||V == 17||V == 22||K == 17||K == 22)0;(G == 17||G == 22||Q == 17||Q == 22||P == 17||P == 22||D == 17||D == 22)0;1;

}

}

//слон рядомbishop_of_king(int x, int y, int flg, work elem)

{M = -1, g1, g2, g3, g4;int s = x, c = y;

//цвет(flg == 1){= 2;= 4;= 5;= 20;

}{= 18;= 19;= 21;= 3;

}

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

do{++;++;((x <= 7 && x >= 0)&&(y <= 7 && y >= 0)){= occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;

}

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

x = s, y =c;

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

do{++;-;((x <= 7 && x >= 0)&&(y <= 7 && y >= 0)){= occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;

}

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

x = s, y =c;

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

do{-;-;((x <= 7 && x >= 0)&&(y <= 7 && y >= 0)){= occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;

}

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

x = s, y =c;

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

do{-;++;((x <= 7 && x >= 0)&&(y <= 7 && y >= 0)){= occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;

}

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

}

//лодья рядомrook_of_king(int x, int y, int flg, work elem)

{M = -1, g1, g2, g3, g4;int s = x, c = y;(flg == 1){= 0;= 4;= 7;= 20;

}{

g1 = 16;= 19;= 23;= 3;

}

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

do{++;(x <= 7 && x >= 0){= occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;

}

x = s, y = c;

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

do{-;(x <= 7 && x >= 0){= occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;

}

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

x = s, y = c;

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

do{-;(y <= 7 && y >= 0){= occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;

}

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

y = c;

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

do{++;(y <= 7 && y >= 0){= occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;

}

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

}

//король рядомking_of_king(int x, int y, int flg, work elem)

{g, M;int a = x, b = y;(flg == 1)= 3;= 20;

//если фигура входит в границы((a+1 >= 0 && a+1 <= 7)&&(b+1 >= 0 && b+1 <= 7)){

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

if(M == g)0;

}

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

if((a-1 >= 0 && a-1 <= 7)&&(b-1 >= 0 && b-1 <= 7)){= occupied_space(a-1, b-1, elem);

if(M == g)0;

}

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

if((a+1 >= 0 && a+1 <= 7)&&(b-1 >= 0 && b-1 <= 7)){= occupied_space(a+1, b-1, elem);

if(M == g)0;

}

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

if((a-1 >= 0 && a-1 <= 7)&&(b+1 >= 0 && b+1 <= 7)){= occupied_space(a-1, b+1, elem);

if(M == g)0;

}

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

if(a-1 >= 0 && a-1 <= 7){= occupied_space(a-1, b, elem);

if(M == g)0;

}

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

if(a+1 >= 0 && a+1 <= 7){= occupied_space(a+1, b, elem);

if(M == g)0;

}

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

if(b+1 >= 0 && b+1 <= 7){= occupied_space(a, b+1, elem);

if(M == g)0;

}

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

if(b-1 >= 0 && b-1 <= 7){= occupied_space(a, b-1, elem);(M == g)0;

}1;

}

//связывающая подпрограмма для короляcommunication_king(int k, int c, int f, work el){(king_of_king(k, c, f, el)){(pawn_of_king(k, c, f, el)){(rook_of_king(k, c, f, el)){(bishop_of_king(k, c, f, el)){(kNight_of_king(k, c, f, el))1;

}

}

}

}0;

}

//корольking(stack **B, int a, int c, int f, work ell)

{int a1 = a, b1 = c;W_1 = 16, B_1 = 0, g1, g2, M;

//цвет(f == 1){= B_1;= B_1 + 15;

}{

g1 = W_1;= W_1 + 15;

}

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

//если фигура входит в границы((a1+1 >= 0 && a1+1 <= 7)&&(b1+1 >= 0 && b1+1 <= 7)){

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

if(communication_king(a1+1, b1+1, f, ell)){= occupied_space(a1+1, b1+1, ell);((M >= g1 && M <= g2)|| M == -1)_stack(&(*B), a1+1, b1+1);

}

}

//если фигура входит в границы((a1-1 >= 0 && a1-1 <= 7)&&(b1-1 >= 0 && b1-1 <= 7)){

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

if(communication_king(a1-1, b1-1, f, ell)){= occupied_space(a1-1, b1-1, ell);((M >= g1 && M <= g2)|| M == -1)_stack(&(*B), a1-1, b1-1);

}

}

//если фигура входит в границы((a1+1 >= 0 && a1+1 <= 7)&&(b1-1 >= 0 && b1-1 <= 7)){

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

if(communication_king(a1+1, b1-1, f, ell)){= occupied_space(a1+1, b1-1, ell);((M >= g1 && M <= g2)|| M == -1)_stack(&(*B), a1+1, b1-1);

}

}

//если фигура входит в границы((a1-1 >= 0 && a1-1 <= 7)&&(b1+1 >= 0 && b1+1 <= 7)){

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

if(communication_king(a1-1, b1+1, f, ell)){= occupied_space(a1-1, b1+1, ell);((M >= g1 && M <= g2)|| M == -1)_stack(&(*B), a1-1, b1+1);

}

}

//если фигура входит в границы(a1-1 >= 0 && a1-1 <= 7){

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

if(communication_king(a1-1, b1, f, ell)){= occupied_space(a1-1, b1, ell);((M >= g1 && M <= g2)|| M == -1)_stack(&(*B), a1-1, b1);

}

}

//если фигура входит в границы(a1+1 >= 0 && a1+1 <= 7){

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

if(communication_king(a1+1, b1, f, ell)){= occupied_space(a1+1, b1, ell);((M >= g1 && M <= g2)|| M == -1)_stack(&(*B), a1+1, b1);

}

}

//если фигура входит в границы(b1+1 >= 0 && b1+1 <= 7){

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

if(communication_king(a1, b1+1, f, ell)){= occupied_space(a1, b1+1, ell);((M >= g1 && M <= g2)|| M == -1)_stack(&(*B), a1, b1+1);

}

}

//если фигура входит в границы(b1-1 >= 0 && b1-1 <= 7){

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

if(communication_king(a1, b1-1, f, ell)){= occupied_space(a1, b1-1, ell);((M >= g1 && M <= g2)|| M == -1)_stack(&(*B), a1, b1-1);

}

}

}

//ферзьqueen(stack **B, int a, int c, int f,work ell)

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

}

//слонbishop(stack **B, int a, int c, int f, work ell)

{int a1 = a, b1 = c;W_1 = 16, B_1 = 0, g1, g2, g3, M;

//цвет(f == 1){= B_1;= B_1 + 15;= 3;

}{

g1 = W_1;= W_1 + 15;= 20;

}

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

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

do{++;++;= occupied_space(a,c,ell);(((a >= 0 && a <= 7)&&(c >= 0 && c <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a, c);

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

a = a1, c = b1;

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

do{-;-;= occupied_space(a,c,ell);(((a >= 0 && a <= 7)&&(c >= 0 && c <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a, c);

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

a = a1, c = b1;

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

do{-;++;= occupied_space(a,c,ell);(((a >= 0 && a <= 7)&&(c >= 0 && c <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a, c);

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

a = a1, c = b1;

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

do{++;-;= occupied_space(a,c,ell);(((a >= 0 && a <= 7)&&(c >= 0 && c <= 7)) && ((M >= g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a, c);

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

}

//лодьяrook(stack **B, int a, int c, int f, work ell)

{int a1 = a, b1 = c, z1 = -1, z2 = 8;W_1 = 16, B_1 = 0, g1, g2, g3, M;

//цвет(f == 1){= B_1;= B_1 + 15;= 3;

}{

g1 = W_1;= W_1 + 15;= 20;

}

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

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

do{++;= occupied_space(a,c,ell);((a > z1 && a < z2) && ((M >= g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a, c);

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

a = a1, c = b1;

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

do{-;= occupied_space(a,c,ell);((a > z1 && a < z2) && ((M >= g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a, c);

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

a = a1, c = b1;

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

do{-;= occupied_space(a,c,ell);((c > z1 && c < z2) && ((M >= g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a, c);

}while((M == -1) && ((c > z1) && (c < z2)) && M != g3);

a = a1, c = b1;

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

do{++;= occupied_space(a,c,ell);(((c > z1) && (c < z2)) && ((M >= g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a, c);

}while((M == -1) && ((c > z1) && (c < z2)) && M != g3);

}

//коньkNight(stack **B, int a, int c, int f, work ell)

{int a1 = a, b1 = c;W_1 = 16, B_1 = 0, g1, g2, g3, M;

//цвет(f == 1){= B_1;= B_1 + 15;= 3;

}{

g1 = W_1;= W_1 + 15;= 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)_stack(&(*B), a1+2, b1-1);= 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)_stack(&(*B), a1+2, b1+1);= 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)_stack(&(*B), a1-2, b1+1);= 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)_stack(&(*B), a1-2, b1-1);= 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)_stack(&(*B), a1-1, b1-2);= 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)_stack(&(*B), a1+1, b1-2);= 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)_stack(&(*B), a1-1, b1+2);= 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)_stack(&(*B), a1+1, b1+2);

}

//пешкаpawn(stack **B, int a, int c, int f,work ell)

{int a1 = a, b1 = c;W_1 = 16, B_1 = 0, g1, g2, g3, M;

//цвет(f == 1){= B_1;= B_1 + 15;= 3;(c == 6){

//одна вперёд= occupied_space(a1,b1-1,ell);((b1-1 >= 0 && b1-1 <= 7) && (M == -1)){_stack(&(*B), a1, b1-1);

//две вперёд= occupied_space(a1,b1-2,ell);((b1-2 >= 0 && b1-2 <= 7) && (M == -1))_stack(&(*B), a1, b1-2);

}

//одна влево= occupied_space(a1-1,b1-1,ell);((a1-1 >= 0 && a1-1 <= 7) && (b1-1 >= 0 && b1-1 <= 7) && (M >= g1 && M <= g2) && M != g3)_stack(&(*B), a1-1, b1-1);

//одна вправо= occupied_space(a1+1,b1-1,ell);((a1+1 >= 0 && a1+1 <= 7) && (b1-1 >= 0 && b1-1 <= 7) && (M >= g1 && M <= g2) && M != g3)_stack(&(*B), a1+1, b1-1);

}{

//одна вперёд= occupied_space(a1,b1-1,ell);((b1-1 >= 0 && b1-1 <= 7) && (M == -1))_stack(&(*B), a1, b1-1);

//одна влево= occupied_space(a1-1,b1-1,ell);((a1-1 >= 0 && a1-1 <= 7) && (b1-1 >= 0 && b1-1 <= 7) && (M >= g1 && M <= g2) && M != g3)_stack(&(*B), a1-1, b1-1);

//одна вправо= occupied_space(a1+1,b1-1,ell);((a1+1 >= 0 && a1+1 <= 7) && (b1-1 >= 0 && b1-1 <= 7) && (M >= g1 && M <= g2) && M != g3)_stack(&(*B), a1+1, b1-1);

}

}{= W_1;= W_1 + 15;= 20;(c == 1){

//одна вперёд= occupied_space(a1,b1+1,ell);((b1+1 >= 0 && b1+1 <= 7) && (M == -1)){_stack(&(*B), a1, b1+1);

//две вперёд= occupied_space(a1,b1+2,ell);((b1+2 >= 0 && b1+2 <= 7) && (M == -1))_stack(&(*B), a1, b1+2);

}

//одна влево= occupied_space(a1-1,b1+1,ell);((a1-1 >= 0 && a1-1 <= 7) && (b1+1 >= 0 && b1+1 <= 7) && (M >= g1 && M <= g2) && M != g3)_stack(&(*B), a1-1, b1+1);

//одна вправо= occupied_space(a1+1,b1+1,ell);((a1+1 >= 0 && a1+1 <= 7) && (b1+1 >= 0 && b1+1 <= 7) && (M >= g1 && M <= g2) && M != g3)_stack(&(*B), a1+1, b1+1);

}{

//одна вперёд= occupied_space(a1,b1+1,ell);((b1+1 >= 0 && b1+1 <= 7) && (M == -1))_stack(&(*B), a1, b1+1);

//одна влево= occupied_space(a1-1,b1+1,ell);((a1-1 >= 0 && a1-1 <= 7) && (b1+1 >= 0 && b1+1 <= 7) && (M >= g1 && M <= g2) && M != g3)_stack(&(*B), a1-1, b1+1);

//одна вправо= occupied_space(a1+1,b1+1,ell);((a1+1 >= 0 && a1+1 <= 7) && (b1+1 >= 0 && b1+1 <= 7) && (M >= g1 && M <= g2) && M != g3)_stack(&(*B), a1+1, b1+1);

}

}

}

//копирование стекаcopying(stack *Q1, stack **Q2)

{(Q1 != NULL) {(*Q2 == NULL){

*Q2 = new stack;

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

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

(*Q2)->next = NULL;

}{*R = new stack;>X = Q1->X;>Y = Q1->Y;>next = (*Q2);

(*Q2) = R;

}= Q1->next;

}

}

//в стекin_stack(stack **Q, int x_1, int y_1)

{(*Q == NULL){

*Q = new stack;

(*Q)->X = x_1;

(*Q)->Y = y_1;

(*Q)->next = NULL;

}{*R = new stack;>X = x_1;>Y = y_1;>next = *Q;

*Q = R;

}

}

//из стекаout_stack(stack**Q, int *x_1, int *y_1)

{(*Q == NULL)0;

*x_1 = (*Q)->X;

*y_1 = (*Q)->Y;*N = *Q;

*Q = (*Q)->next;N;1;

}

//поиск в стекеsearch_stack(stack*Q, int n, int m)

{(Q != NULL){(Q->X == n && Q->Y == m)1;= Q->next;

}0;

}

/*Form1.h*/

#pragma once

#include<string.h>

#include <stdio.h>

#include "chessman.h"FILE *fl, *fll, *fll2, *input;C, old_X, old_Y;// фигура для пп clikchess {namespace System;namespace System::ComponentModel;namespace System::Collections;namespace System::Windows::Forms;namespace System::Data;namespace System::Drawing;

/// <summary>

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

/// </summary>fig[63];ref class Form1 : public System::Windows::Forms::Form

{:

//необходимая информация о фигурхinput_fl(color_1 *B, color_2 *W)

{k = 0, q = 0;ch[4];((fl = fopen("fl.txt", "r")) == NULL)("error");{(fl,"%s",&B->chessBlack);(fl,"%s",&W->chessWhite);((k < 16) && fscanf(fl,"%s",&ch))

{(B->Bcolor[k].chessman, ch);>Bcolor[k].No = k;++;

}(fscanf(fl,"%s",&ch) != EOF)

{(W->Wcolor[q].chessman, ch);>Wcolor[q].No = k;

q++;++;

}

}(fl);

}

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

void initchess()

{(int i = 0; i < 32; i++)[i]= -5;();

}initznak()

{(int i = 32; i < 63; i++)[i]= -5;

}

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

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

{[i] = y*8+x;

}

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

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

{

//инициализация символов хода();ell;

stack *backup = NULL;flg = 0;

//вспомогательные элементы(&ell);_stakc(&backup);

//выбор фигуры(backup == NULL)

{= occupied_space(a, b, ell);

if(C>15) //белые= 1;

//королль(C == 3 || C == 20)

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

//ферзь(C == 4 || C == 19)(&(*course), a, b, flg,ell);

//слон((C == 2 || C == 5) || (C == 18 || C == 21))(&(*course), a, b, flg,ell);

//лодья((C == 0 || C == 7) || (C == 16 || C == 23))(&(*course), a, b, flg,ell);

//конь((C == 1 || C == 6) || (C == 17 || C == 22))(&(*course), a, b, flg,ell);

//пешка((C >= 24 && C <= 31) || (C >= 8 && C <= 15))(&(*course), a, b, flg,ell);

//вспомогательные элементы(*course, &backup);

openfile_stakc(&backup);_X = a, old_Y = b;

}

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

{U, d = 0, h = 0;

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

if(search_stack(backup, a, b)){= occupied_space(old_X, old_Y, ell);(ell.table[d].chessmanNo != U){++;

}= occupied_space(a, b, ell);

//место пусто переместить(U == -1){

ell.table[d].x = a;.table[d].y = b;

}

//место занято срубить{(ell.table[h].chessmanNo != U)++;.table[h].x = -5;.table[h].y = -5;.table[d].x = a;.table[d].y = b;

}

//смена изображения();(int j = 0; j < ell.n; j++)(ell.table[j].chessmanNo,ell.table[j].y,ell.table[j].x);

}

//вспомогательные элементы(out_stack(&backup, &old_X, &old_Y))_X = 0, old_Y = 0;_stakc(&backup);(ell);

}

}

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

{_1 Bl;_2 Wh;elem;_fl(&Bl,&Wh);(Bl, Wh, &elem);(elem);(int j = 0; j < elem.n; j++)

//выполнение вывода пользовательской расстановки фигур(elem.table[j].chessmanNo, elem.table[j].y, elem.table[j].x);

}(void)

{();();();

}:

~Form1()

{(components)

{components;

}

}: System::Windows::Forms::PictureBox^ pictureBox1;::::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated codeInitializeComponent(void)

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

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->pictureBox1))->BeginInit();>SuspendLayout();

//

// pictureBox1

//>pictureBox1->BackColor = System::Drawing::Color::White;>pictureBox1->Location = System::Drawing::Point(12, 12);>pictureBox1->Name = L"pictureBox1";>pictureBox1->Size = System::Drawing::Size(400, 400);>pictureBox1->TabIndex = 0;>pictureBox1->TabStop = false;>pictureBox1->Paint += gcnew System::Windows::Forms::PaintEventHandler(this, &Form1::pictureBox1_Paint);>pictureBox1->MouseClick += gcnew System::Windows::Forms::MouseEventHandler(this,&Form1::pictureBox1_MouseClick);

// Form1

//>AutoScaleDimensions = System::Drawing::SizeF(6, 13);>AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;>ClientSize = System::Drawing::Size(424, 420);>Controls->Add(this->pictureBox1);>FormBorderStyle = System::Windows::Forms::FormBorderStyle::FixedSingle;>MaximizeBox = false;>Name = L"Form1";>Text = L"Form1";

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->pictureBox1))->EndInit();>ResumeLayout(false);

}

#pragma endregion: System::Void pictureBox1_Paint(System::Object^ sender, System::Windows::Forms::PaintEventArgs^ e) {^ g = e->Graphics;n = 0;(int i = 0; i < 8; i++)

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

{(n % 2 == 1)>FillRectangle(Brushes::Brown, j * 50, i * 50, 50, 50);>FillRectangle(Brushes::Wheat, j * 50, i * 50, 50, 50);++;

}++;

}::Drawing::Font^ drawFont = gcnew System::Drawing::Font( "Arial",29 );>DrawString(L"♜", drawFont, Brushes::Black, fig[0] % 8 * 50, fig[0] / 8 * 50);>DrawString(L"♞", drawFont, Brushes::Black, fig[1] % 8 * 50, fig[1] / 8 * 50);>DrawString(L"♝", drawFont, Brushes::Black, fig[2] % 8 * 50, fig[2] / 8 * 50);>DrawString(L"♚", drawFont, Brushes::Black, fig[3] % 8 * 50, fig[3] / 8 * 50);>DrawString(L"♛", drawFont, Brushes::Black, fig[4] % 8 * 50, fig[4] / 8 * 50);>DrawString(L"♝", drawFont, Brushes::Black, fig[5] % 8 * 50, fig[5] / 8 * 50);>DrawString(L"♞", drawFont, Brushes::Black, fig[6] % 8 * 50, fig[6] / 8 * 50);>DrawString(L"♜", drawFont, Brushes::Black, fig[7] % 8 * 50, fig[7] / 8 * 50);(int i = 0; i < 8; i++)>DrawString(L"♟", drawFont, Brushes::Black, fig[8 + i] % 8 * 50, fig[8 + i] / 8 * 50);>DrawString(L"♖", drawFont, Brushes::Black, fig[16] % 8 * 50, fig[16] / 8 * 50);>DrawString(L"♘", drawFont, Brushes::Black, fig[17] % 8 * 50, fig[17] / 8 * 50);>DrawString(L"♗", drawFont, Brushes::Black, fig[18] % 8 * 50, fig[18] / 8 * 50);>DrawString(L"♕", drawFont, Brushes::Black, fig[19] % 8 * 50, fig[19] / 8 * 50);>DrawString(L"♔", drawFont, Brushes::Black, fig[20] % 8 * 50, fig[20] / 8 * 50);>DrawString(L"♗", drawFont, Brushes::Black, fig[21] % 8 * 50, fig[21] / 8 * 50);>DrawString(L"♘", drawFont, Brushes::Black, fig[22] % 8 * 50, fig[22] / 8 * 50);>DrawString(L"♖", drawFont, Brushes::Black, fig[23] % 8 * 50, fig[23] / 8 * 50);(int i = 24; i < 32; i++)>DrawString(L"♙", drawFont, Brushes::Black, fig[i] % 8 * 50, fig[ i] / 8 * 50);(int i = 32; i < 63; i++)>DrawString(L"✕", drawFont, Brushes::Blue, fig[i] % 8 * 50, fig[i] / 8 * 50);

}: System::Void pictureBox1_MouseClick(System::Object^ sender, System::Windows::Forms::MouseEventArgs^ e) {*poss_course = NULL;x1 = e->X / 50, y1 = e->Y / 50;(x1, y1, &poss_course);(poss_course != NULL){(int s = 0, k = 0, z = 32; out_stack(&poss_course, &s, &k); z++)(z, k, s);

}->Refresh();

}

};

}

/*main.cpp*/

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

#include "stdafx.h"

#include "Form1.h"

#include "chessman.h"namespace chess;

[STAThreadAttribute]main(array<System::String ^> ^args)

{

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

Application::EnableVisualStyles();::SetCompatibleTextRenderingDefault(false);

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

Application::Run(gcnew Form1());0;

}

/*chessman.cpp*/

#ifndef CHESSMAN_H

#define CHESSMAN_H

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

char chessman [4];No;

};color_1 {Bcolor [16];chessBlack [8];

};

//Таблица с белыми фигурамиWhite {chessman [4];No;

};color_2 {Wcolor [16];chessWhite [7];

};

};work {table [33];n;

};stack {*next;X;Y;

};myscanf(color_1 B, color_2 W, work *el);

//королльking(stack **B, int a, int c, int f,work ell);

//ферзьqueen(stack **B, int a, int c, int f,work ell);

//слонbishop(stack **B, int a, int c, int f,work ell);

//лодьяrook(stack **B, int a, int c, int f,work ell);

//коньkNight(stack **B, int a, int c, int f,work ell);

//пешкаpawn(stack **B, int a, int c, int f,work ell);

//копирование стекаcopying(stack *Q1, stack **Q2);

//в стекin_stack(stack **Q, int x, int y);

//из стекаout_stack(stack**Q, int *x, int *y);

//что в данной клеткеoccupied_space(int K1, int K2, work ell);openfile(work ell);closefile(work *ell);openfile_stakc(stack **B);closefil_stakc(stack **B);search_stack(stack*Q, int n, int m);

#endif

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

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

Литература

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