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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
#1

Китайские шашки. Перебор - C++

11.03.2012, 23:23. Просмотров 2205. Ответов 2

Суть китайских шашек такова: есть поле(см. рисунок) и можно перепрыгивать через фишку, если поле за ней свободно. При этом фишка, через которую перепрыгнули, убирается. Нужно убрать все фишки.
Китайские шашки. Перебор Китайские шашки. Перебор
Сначала я сделал перебор на основе очереди, но он ел слишком много памяти (и это без вывода решений, просто проверка существования)
код
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
#include <iostream>
#include <vector>
#include <queue>
///////////////////////////////////////////////////////////////////////////////
 
using namespace std;
 
///////////////////////////////////////////////////////////////////////////////
 
typedef vector<int  > T_vec;
typedef vector<T_vec> T_mtr;
 
///////////////////////////////////////////////////////////////////////////////
 
enum {EMPTY, POINT, NOTBOARD};
 
///////////////////////////////////////////////////////////////////////////////
 
const int SIZE = 9;
 
///////////////////////////////////////////////////////////////////////////////
 
const int  stepi[] = { 1,-1, 0, 0};
const int  stepj[] = { 0, 0, 1,-1};
 
///////////////////////////////////////////////////////////////////////////////
 
inline bool endOfGame(T_mtr& m)
{
    for(int i = 0; i < m.size(); i++)
        for(int j = 0; j < m[i].size(); j++)
            if(m[i][j] == POINT)
                return false;
    return true;
}
 
///////////////////////////////////////////////////////////////////////////////
 
int main()
{
    T_mtr board(SIZE, T_vec(SIZE, NOTBOARD));
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < SIZE; j++)
        {
            board[3+i][j] = POINT;
            board[j][3+i] = POINT;
        }
    board[4][4] = EMPTY;
    
    queue<T_mtr> moves;
    moves.push(board);
    int mv = 0;
    while(!moves.empty())
    {
        T_mtr now = moves.front();
        moves.pop();
        if(endOfGame(now))
        {
            cout << "Find solution!" << endl;
            break;
        }
        //THIS IS BRUTE FORCE!!!!111
        for(int i = 0; i < now.size(); i++)
            for(int j = 0; j < now[i].size(); j++)
                if(now[i][j] == POINT)
                    for(int st = 0; st < sizeof stepi / sizeof *stepi; st++)
                    {
                        int newi  = i +   stepi[st];
                        int newj  = j +   stepj[st];
                        int newdi = i + 2*stepi[st];
                        int newdj = j + 2*stepj[st];
                        if( newdi >= 0 && newdi < SIZE &&
                            newdj >= 0 && newdj < SIZE &&
                            now[newi ][newj ] == POINT &&
                            now[newdi][newdj] == EMPTY)
                        {
                            T_mtr temp = now;
                            temp[i    ][j    ] = EMPTY;
                            temp[newi ][newj ] = EMPTY;
                            temp[newdi][newdj] = POINT;
                            moves.push(temp);
                        }
                    }
    }
    return 0;
}

потом просто заменил очередь на стек (теперь программа потребляет порядка 2 мегабайт)
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
#include <iostream>
#include <vector>
#include <stack>
///////////////////////////////////////////////////////////////////////////////
 
using namespace std;
 
///////////////////////////////////////////////////////////////////////////////
 
typedef vector<int  > T_vec;
typedef vector<T_vec> T_mtr;
 
///////////////////////////////////////////////////////////////////////////////
 
enum {EMPTY, POINT, NOTBOARD};
 
///////////////////////////////////////////////////////////////////////////////
 
const int SIZE = 9;
 
///////////////////////////////////////////////////////////////////////////////
 
const int  stepi[] = { 1,-1, 0, 0};
const int  stepj[] = { 0, 0, 1,-1};
 
///////////////////////////////////////////////////////////////////////////////
 
inline bool endOfGame(T_mtr& m)
{
    for(int i = 0; i < m.size(); i++)
        for(int j = 0; j < m[i].size(); j++)
            if(m[i][j] == POINT)
                return false;
    return true;
}
 
///////////////////////////////////////////////////////////////////////////////
 
int main()
{
    T_mtr board(SIZE, T_vec(SIZE, NOTBOARD));
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < SIZE; j++)
        {
            board[3+i][j] = POINT;
            board[j][3+i] = POINT;
        }
    board[4][4] = EMPTY;
    
    stack<T_mtr> moves;
    moves.push(board);
    int mv = 0;
    while(!moves.empty())
    {
        T_mtr now = moves.top();
        moves.pop();
        if(endOfGame(now))
        {
            cout << "Find solution!" << endl;
            break;
        }
        //THIS IS BRUTE FORCE!!!!111
        for(int i = 0; i < now.size(); i++)
            for(int j = 0; j < now[i].size(); j++)
                if(now[i][j] == POINT)
                    for(int st = 0; st < sizeof stepi / sizeof *stepi; st++)
                    {
                        int newi  = i +   stepi[st];
                        int newj  = j +   stepj[st];
                        int newdi = i + 2*stepi[st];
                        int newdj = j + 2*stepj[st];
                        if( newdi >= 0 && newdi < SIZE &&
                            newdj >= 0 && newdj < SIZE &&
                            now[newi ][newj ] == POINT &&
                            now[newdi][newdj] == EMPTY)
                        {
                            T_mtr temp = now;
                            temp[i    ][j    ] = EMPTY;
                            temp[newi ][newj ] = EMPTY;
                            temp[newdi][newdj] = POINT;
                            mv++;
                            if(mv%1000 == 0)
                                cout << "Valid move: " << mv << endl;
                            moves.push(temp);
                        }
                    }
    }
    return 0;
}
на варианте с очередью я подождал до перебора 2 млн. вариантов, а на модификации со стеком до 200 млн.

И наконец вопрос: как эффективно решить эту задачу?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2012, 23:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Китайские шашки. Перебор (C++):

Игра шашки: Исправить копирование шашки заместо переставления - C++
Почти написал шашки на с++, но есть одна проблема,При захвате шашки оно ейо не перставляет а копирует,вот код: //...

Китайские номера - C++
Еше одна, буду благодарен за помощь. В Китае восьмерка считается счастливым числом и люди стремятся заполучить автомобильные номера,...

Китайские символы в реестре - C++
Есть небольшая программа которая записывает некоторое приложение в автозагрузку, и для этого редактирует реестр. Проблема в том что...

Китайские иероглифы в файле - C++
Вечер в хату, падсаны. Заметил очень забавную вещь: вроде ничего такого в коде странного нет, но почему то в файл выводятся одни...

C++ , китайские данные - C++
В общем есть у меня Wave файл - я считал из него Чанк DATA , а в этом чанке находятся типа звуковые данные , дык вот считал я их - и увидел...

Китайские иероглифы в консольном приложении - C++
Вопрос: можно ли вывести в консоли китайские иероглифы, или например специфичные немецкие буквы стандартами языка си или же с++. Может...

2
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
13.03.2012, 13:59  [ТС] #2
вариант с запоминанием решения:
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
#include <iostream>
#include <vector>
#include <stack>
///////////////////////////////////////////////////////////////////////////////
 
using namespace std;
 
///////////////////////////////////////////////////////////////////////////////
 
struct move
{
    int fromi;
    int fromj;
    int toi;
    int toj;
    
    move(): 
        fromi(0), fromj(0), toi(0), toj(0) {};
    move(int _fi, int _fj, int _ti, int _tj):
        fromi(_fi), fromj(_fj), toi(_ti), toj(_tj) {};
};
 
///////////////////////////////////////////////////////////////////////////////
 
typedef vector<move > T_mov;
typedef vector<int  > T_vec;
typedef vector<T_vec> T_mtr;
 
///////////////////////////////////////////////////////////////////////////////
 
enum {EMPTY, POINT, NOTBOARD};
 
///////////////////////////////////////////////////////////////////////////////
 
const int SIZE = 9;
 
///////////////////////////////////////////////////////////////////////////////
 
const int  stepi[] = { 1,-1, 0, 0};
const int  stepj[] = { 0, 0, 1,-1};
 
///////////////////////////////////////////////////////////////////////////////
 
inline bool endOfGame(T_mtr& m)
{
    for(int i = 0; i < m.size(); i++)
        for(int j = 0; j < m[i].size(); j++)
            if(m[i][j] == POINT)
                return false;
    return true;
}
 
///////////////////////////////////////////////////////////////////////////////
 
int main()
{
    T_mtr board(SIZE, T_vec(SIZE, NOTBOARD));
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < SIZE; j++)
        {
            board[3+i][j] = POINT;
            board[j][3+i] = POINT;
        }
    board[4][4] = EMPTY;
    
    stack< pair< T_mtr, T_mov > > moves;
    T_mov start;
    moves.push(make_pair(board, start));
    int mv = 0;
    while(!moves.empty())
    {
        pair< T_mtr, T_mov > now = moves.top();
        T_mtr nowBoard = now.first;
        T_mov nowWay   = now.second;
        moves.pop();
        if(endOfGame(nowBoard))
        {
            cout << "Find solution!" << endl;
            //print way
            break;
        }
        //THIS IS BRUTE FORCE!!!!111
        for(int i = 0; i < nowBoard.size(); i++)
            for(int j = 0; j < nowBoard[i].size(); j++)
                if(nowBoard[i][j] == POINT)
                    for(int st = 0; st < sizeof stepi / sizeof *stepi; st++)
                    {
                        int newi  = i +   stepi[st];
                        int newj  = j +   stepj[st];
                        int newdi = i + 2*stepi[st];
                        int newdj = j + 2*stepj[st];
                        if( newdi >= 0 && newdi < SIZE &&
                            newdj >= 0 && newdj < SIZE &&
                            nowBoard[newi ][newj ] == POINT &&
                            nowBoard[newdi][newdj] == EMPTY)
                        {
                            T_mtr tempBoard = nowBoard;
                            tempBoard[i    ][j    ] = EMPTY;
                            tempBoard[newi ][newj ] = EMPTY;
                            tempBoard[newdi][newdj] = POINT;
                            T_mov tempWay = nowWay;
                            move lastMove(i, j, newdi, newdj);
                            tempWay.push_back(lastMove);
                            moves.push(make_pair(tempBoard, tempWay));
                            if(mv%1000 == 0)
                                cout << "Valid move: " << mv << endl;
                            mv++;
                        }
                    }
    }
    return 0;
}
1
exstazi
Сообщений: n/a
08.03.2013, 20:47 #3
Mayonez, Ты нашел решение своей задачи?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.03.2013, 20:47
Привет! Вот еще темы с ответами:

Как вывести китайские иероглифы в консоль? - C++
Здравствуйте, подскажите как вывести в консоль Виндоус какой-нибудь китайский иероглиф. Например, свастику 卐 .(ничего плохого не подумайте,...

Как отобразить Китайские иероглифы в Dev-C++ ? - C++
Всем привет,в програме написанной на DEV-C++ нужно отобразить китайские иероглифы, при каждом запуске програмы вместо иероглифов появляются...

Вывод в документ: китайские иероглифа вместо русских или английских букв - C++
В коде какато фигня. Он написан и по идее работает, но вот с языком вывода проблема. Когда записываешь что-то в документ он записывает...

шашки C++ - C++
О великие гуру,я взываю вашей помощи. Хочу написать шашки на C++,но пока не особо представляю,что к чему. А именно: как сделать...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru