Форум программистов, компьютерный форум CyberForum.ru

Определить все ходы для белой шашки. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.91
Хакер
6 / 6 / 0
Регистрация: 15.03.2009
Сообщений: 83
02.10.2009, 19:58     Определить все ходы для белой шашки. #1
На шашечном поле в произвольном порядке расставлены шашки. Для выбранной пользователем белой шашки определить все ее возможные ходы. Учесть, что за один шаг белая шашка может сбить несколько черных шашек.Нужно использовать рекурсию.
Вот сижу и думаю как эту рекурсию использовать и в каком месте.Что это такое я интуитивно догадываюсь,немного порылся в нете,но применить к данной задаче не могу.Может кто подскажет где и как или даст ссылку на инфу.Буду благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2009, 19:58     Определить все ходы для белой шашки.
Посмотрите здесь:

Шашки C++
C++ Для заданной матрицы определить все седловые точки
шашки C++ C++
Ходы шахматного коня C++
Для натурального числа определить истинность предиката «все цифры в записи числа равны» C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
02.10.2009, 23:08     Определить все ходы для белой шашки. #2
Наверное если срубил черную шашку, то дальше можн рекурсивно вызвать туже процедуру чтобы она проверила - нельзя ли срубить еще одну шашку.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
03.10.2009, 10:41     Определить все ходы для белой шашки. #3
Ну, слушай, такое дело раз.

Во-первых, создай матрицу 8x8 и как-то сыммитируй на ней шашки. Заполни то есть.
Вручную, ещё как-то.
Допустим, если элемент равен 1, это чёрная шашка, если 2, то белая, если 0- никакая.
И заполняяй по шашечным правилам.
Это уж ты сам думай как.

В программме будет две функции
1) основная (рекурсивная) osn
2) вспомогательная vsp

Вот схема

osn {
vsp ()
osn
}

Всомогательная функция будет показывать, куда шашке можно ходить (условимся, что она не дамка)
То есть каждая шашка может потенциально сделать 8 ходов
pramo_napravo_mal;
pramo_napravo_bol; //Это когда перепрыгивает
pramo_nalevo_mal;
pramo_nalevo_boll;
nazad_napravo_mal;
nazad_napravo_bol;
nazad_nalevo_mal;
nazad_nalevo_boll;

Теперь смотри. Если одна из этих величин равна 1, то шашка может туда ходить, если равна 0, то не может.
То, естть, к примеру, получаешь такие значения

pramo_napravo_mal==0;
pramo_napravo_bol==1; //Это когда перепрыгивает
pramo_nalevo_mal==0;
pramo_nalevo_boll==0;
nazad_napravo_mal==1;
nazad_napravo_bol==0;
nazad_nalevo_mal==0;
nazad_nalevo_boll==1;

...Как узнать, куда шашка может сходить, а куда нет?
Для этого существует vsp
В неё передаются указатели на эти переменные и координаты шашки.
Вот, собственно, и начинаются мытраства.
В функции vsp, принимающей указатели на эти переменные ты должен определить каждое из 8-ми значений, учитывая

1)координаты шашки
2)координаты других шашек (массив-то глобальный и виден отовсюду)
Это ты уж сам сиди и думай, как всё сделать
Схема будет так выглядеть с учётом вышесказанного:

osn {

bool pramo_napravo_mal==0;
bool pramo_napravo_bol==1; //Это когда перепрыгивает
bool pramo_nalevo_mal==0;
bool pramo_nalevo_boll==0;
bool nazad_napravo_mal==1;
bool nazad_napravo_bol==0;
bool nazad_nalevo_mal==0;
bool nazad_nalevo_boll==1;

vsp (&pramo_napravo_mal //+ адреса всех этих переменных + координаты шашки)

osn ()
}


Ну, и, наконец, по вызову osn
Вызываешь так

if (pramo_napravo_mal) {
osn ()
}

if (pramo_napravo_bol) {
osn ()
}

...И так далее, до конца. 8 вызовов должно быть
В функцию osn передаются координаты шашки, куда можно сходить.
То есть если у тебя текущие параметры (0, 1), и, допустим nazad_napravo_mal==1, то пишешь

if (nazad_napravo_mal) {
osn (2, 3)
}

...Ну вот так и прыгаешь, пока все параметры не станут равны 0.
Введи переменную какую-нибудь пусть ходы подсчитывет. Учитывай всё.

...Да. Самый первый вызов функции osn такой:
osn (координаты шашки)

Спрашивай, что непонятно!
Хакер
6 / 6 / 0
Регистрация: 15.03.2009
Сообщений: 83
04.10.2009, 15:57  [ТС]     Определить все ходы для белой шашки. #4
Что-то плохо понятно.Я сделал поле 8х8,сделал ввод координат шашек и сделал определение возможного хода(право лево,с учетом занятых клеток),но все без рекурсии и не могу пока сделать функцию(рекурсивную)
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
04.10.2009, 17:30     Определить все ходы для белой шашки. #5
Бум учиться.
Давай сюда код с комментариями и внятно говори, в чём трудности.
XuTPbIu_MuHTAu
Эксперт C++
 Аватар для XuTPbIu_MuHTAu
2219 / 734 / 10
Регистрация: 27.05.2008
Сообщений: 1,507
05.10.2009, 02:35     Определить все ходы для белой шашки. #6
Хакер, Все просто.Опиши функцию для одного хода,после чего добавь вызов ее для себя же в случае,если этот ход кого-то захавал.При этом,перед вызовом "убирай "съеденную шашку,ходящую шашку "перемещай"а после вызова возвращай съеденную и переместившуюся на изначальные позиции.

Получится,что рекурсия как бы раскатает какой-то вариант,каждый раз закатывая его обратно после того,как он рассмотрен,возвращаясь к исходной позиции и проверяя другие возможные ходы из текущей глубины перебора.
Nec_Too
0 / 0 / 0
Регистрация: 01.06.2010
Сообщений: 3
01.06.2010, 23:30     Определить все ходы для белой шашки. #7
Хакер, а не осталось работающей программы? был бы очень признателен...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.06.2010, 15:42     Определить все ходы для белой шашки.
Еще ссылки по теме:

C++ Игра "Борьба за жизнь". Цель игры – убрать с доски все шашки противника
C++ Необходимо организовать ИИ (Искусственный Интеллект) для игры шашки
Игра шашки: Исправить копирование шашки заместо переставления C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,686
03.06.2010, 15:42     Определить все ходы для белой шашки. #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
//На шашечном поле в произвольном порядке расставлены шашки. 
//Для выбранной пользователем белой шашки определить все ее возможные ходы. 
//Учесть, что за один шаг белая шашка может сбить несколько черных шашек.
//Нужно использовать рекурсию.
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
 
const int VERT_MIN_VAL = 'a';
const int VERT_MAX_VAL = 'h';
 
const int HORIS_MIN_VAL = '1';
const int HORIS_MAX_VAL = '8';
 
typedef std::string  T_str;
 
enum T_shashka_color
{
    VNE_DOSKI = 0,
    EMPTY,
    WHITE,
    BLACK    
};
 
enum T_napravl
{
    VLEVO,
    VPRAVO,
    NAZAD_VLEVO,
    NAZAD_VPRAVO
};
 
typedef std::map<char, T_shashka_color>  T_doska_vert;
typedef std::map<char, T_doska_vert>     T_shashka_colors;
 
struct T_kletka
{
    char  vert_; //От 'a' до 'h'.   
    char  horis_;//От '1' до '8'.
    
    T_kletka(char  vert = 0, char  horis = 0) : vert_(vert), horis_(horis)
    {}
 
    T_kletka(T_str  str_coord) 
        : vert_(str_coord[0]), horis_(str_coord[1])        
    {}
 
    T_kletka  get_next_1(T_napravl  napravl)
    {
        int  vert_shift   = 0;
        int  horis_shift  = 0;
 
        switch(napravl)
        {
        case VLEVO: 
            vert_shift   = -1;
            horis_shift  =  1;
            break;
        case VPRAVO: 
            vert_shift   = 1;
            horis_shift  = 1;
            break;
        case NAZAD_VLEVO: 
            vert_shift   = -1;
            horis_shift  = -1;
            break;
        case NAZAD_VPRAVO: 
            vert_shift   =  1;
            horis_shift  = -1;
            break;
        default:
            ;           
        }//switch(napravl)
        return T_kletka(vert_ + vert_shift, horis_ + horis_shift);
    }
};//struct T_kletka
 
void  print_kletka(T_kletka  kletka)
{        
    std::cout << kletka.vert_ << kletka.horis_ << ' ';   
}
 
typedef std::vector<T_kletka>  T_path;
 
class T_doska
{
    T_shashka_colors  shashka_colors;
public:
    T_doska()
    {
        for(char vert = VERT_MIN_VAL; vert <= VERT_MAX_VAL; ++vert)
        {
            for(char horis = HORIS_MIN_VAL; horis <= HORIS_MAX_VAL; ++horis)
            {
                shashka_colors[vert][horis] = EMPTY;
            }
        }
    }
 
    bool  is_emty_kletka(T_kletka  kletka)
    {
        return get_shashka_color_ref(kletka) == EMPTY;
    }
 
    void swap_colors
        (
            T_kletka  kletka1,
            T_kletka  kletka2
        )
    {
        T_shashka_color&  color1 = get_shashka_color_ref(kletka1);
        T_shashka_color&  color2 = get_shashka_color_ref(kletka2);
        std::swap(color1, color2);
    }
 
    bool  are_raznocvetn_shashki
        (
            T_kletka  kletka1,
            T_kletka  kletka2
        )
    {
        T_shashka_color  color1 = get_shashka_color_ref(kletka1);
        T_shashka_color  color2 = get_shashka_color_ref(kletka2);
        return    color1 == WHITE && color2 == BLACK
               || color1 == BLACK && color2 == WHITE;       
    }
 
    void  del_shashka(T_kletka  kletka)
    {
        get_shashka_color_ref(kletka) = EMPTY;
    }
 
    void  set_white_shashka(T_kletka  kletka)
    {
        get_shashka_color_ref(kletka) = WHITE;
    }
 
    void  set_black_shashka(T_kletka  kletka)
    {
        get_shashka_color_ref(kletka) = BLACK;
    }
private:
    T_shashka_color&  get_shashka_color_ref(T_kletka  kletka)
    {
        return shashka_colors[kletka.vert_][kletka.horis_];    
    }
};//class T_doska
 
struct T_shashka
{
    void xod
        (            
            T_kletka  kletka,
            T_doska   doska
        )
    {
        T_path  path;
        path.push_back(kletka);       
        xod(VLEVO,  path, doska);
        xod(VPRAVO, path, doska);      
        
        bit(VLEVO,        path, doska);
        bit(VPRAVO,       path, doska);
        bit(NAZAD_VLEVO,  path, doska);
        bit(NAZAD_VPRAVO, path, doska);        
    }
 
    void xod
        (
            T_napravl  napravl,
            T_path     path,
            T_doska    doska
        )
    {        
        T_kletka  cur_kletka   = path.back();
        T_kletka  next_kletka  = cur_kletka.get_next_1(napravl);
        if(doska.is_emty_kletka(next_kletka))
        {                        
            doska.swap_colors(cur_kletka, next_kletka);
            path.push_back(next_kletka);
            print_path(path);            
        }     
    }
 
    void  bit
        (
            T_napravl  napravl,            
            T_path     path,
            T_doska    doska
        )
    {        
        T_kletka  cur_kletka   = path.back();
        T_kletka  next_kletka1 = cur_kletka   .get_next_1(napravl);
        T_kletka  next_kletka2 = next_kletka1 .get_next_1(napravl);
 
        if(doska.are_raznocvetn_shashki(cur_kletka, next_kletka1)
           && doska.is_emty_kletka(next_kletka2))
        {
            doska.swap_colors(cur_kletka, next_kletka2);            
            doska.del_shashka(next_kletka1);         
            path.push_back(next_kletka2);
 
            bit(VLEVO,        path, doska);
            bit(VPRAVO,       path, doska);
            bit(NAZAD_VLEVO,  path, doska);
            bit(NAZAD_VPRAVO, path, doska);
            print_path(path);                           
        }        
    }
 
    void  print_path(const T_path&  path)
    {
        static int xod_count = 0;
        std::cout << "ход " << ++xod_count << ":   ";
        std::for_each(path.begin(), path.end(), print_kletka);
        std::cout << std::endl;    
    }
};//struct T_shashka
 
bool is_correct_str_coord(T_str  str_coord)
{
     return    VERT_MIN_VAL <= str_coord[0]  && str_coord[0] <= VERT_MAX_VAL
            && HORIS_MIN_VAL <= str_coord[1] && str_coord[1] <= HORIS_MAX_VAL;   
}
 
int main()
{   
    std::locale::global(std::locale("rus"));   
    std::cout << "Введите координаты шашек в виде a1, c3, f8 и т.д. "
              << std::endl
              << "Окончание ввода - пустая строка."
              << std::endl;
 
    T_doska  doska;    
    T_str    bel_xodit_str_coord;
    for(;;)
    {
        std::cout << "Координаты белой шашки, делающей ход: ";        
        getline(std::cin, bel_xodit_str_coord);    
        if(bel_xodit_str_coord.empty()) return 0;
        if(is_correct_str_coord(bel_xodit_str_coord))
        {           
            doska.set_white_shashka(bel_xodit_str_coord);
            break;
        }
    }
 
    for(int vvodim_chernye = 0; vvodim_chernye < 2; ++vvodim_chernye)
    {
         std::cout << std::endl
                  << "Введите координаты "
                  << (vvodim_chernye ? "черных" : "белых")
                  << " шашек: "
                  << std::endl;        
 
        for(int i = 1;;)
        {
            std::cout << (vvodim_chernye ? "черная " : "белая ")
                      << i
                      << ": ";
            
            T_str  cur_shash_str_coord;
            getline(std::cin, cur_shash_str_coord);
            if(cur_shash_str_coord.empty()) break;        
            if(is_correct_str_coord(cur_shash_str_coord))
            {        
                vvodim_chernye ? doska.set_black_shashka(cur_shash_str_coord)
                               : doska.set_white_shashka(cur_shash_str_coord);
                ++i;
            }        
        }   
    }//for(bool vvodim_chernye = false; vvodim_chernye <= true; ++vvodim_chernye)
 
    std::cout << std::endl;
    T_shashka  bel_xodit_shash;    
    bel_xodit_shash.xod(bel_xodit_str_coord, doska);  
 
    return 0;
}
Yandex
Объявления
03.06.2010, 15:42     Определить все ходы для белой шашки.
Ответ Создать тему
Опции темы

Текущее время: 02:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru