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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
11.03.2012, 23:23     Китайские шашки. Перебор #1
Суть китайских шашек такова: есть поле(см. рисунок) и можно перепрыгивать через фишку, если поле за ней свободно. При этом фишка, через которую перепрыгнули, убирается. Нужно убрать все фишки.
Китайские шашки. Перебор Китайские шашки. Перебор
Сначала я сделал перебор на основе очереди, но он ел слишком много памяти (и это без вывода решений, просто проверка существования)
код
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 млн.

И наконец вопрос: как эффективно решить эту задачу?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2012, 23:23     Китайские шашки. Перебор
Посмотрите здесь:

вывод в документ. китайские иероглифа вместо русских или английских букв C++
Шашки C++
шашки C++ C++
C++ Китайские иероглифы в консольном приложении
Как вывести китайские иероглифы в консоль? C++
Китайские символы в реестре C++
Игра шашки: Исправить копирование шашки заместо переставления C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 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;
}
exstazi
Сообщений: n/a
08.03.2013, 20:47     Китайские шашки. Перебор #3
Mayonez, Ты нашел решение своей задачи?
Yandex
Объявления
08.03.2013, 20:47     Китайские шашки. Перебор
Ответ Создать тему

Метки
китайские шашки, перебор
Опции темы

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