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

@Mayonez · Регистрация: 26.12.2009

Студворк — интернет-сервис помощи студентам

Суть китайских шашек такова: есть поле(см. рисунок) и можно перепрыгивать через фишку, если поле за ней свободно. При этом фишка, через которую перепрыгнули, убирается. Нужно убрать все фишки.

Сначала я сделал перебор на основе очереди, но он ел слишком много памяти (и это без вывода решений, просто проверка существования)

код

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 млн.

И наконец вопрос: как эффективно решить эту задачу?

@Mayonez · 13.03.2012, 13:59 **[ТС]**

вариант с запоминанием решения:

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;
}

08.03.2013, 20:47

Mayonez, Ты нашел решение своей задачи?

Новые блоги и статьи Все статьи Все блоги /
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .

exstazi
	08.03.2013, 20:47
	Mayonez, Ты нашел решение своей задачи?