С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.77/30: Рейтинг темы: голосов - 30, средняя оценка - 4.77
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,538
1

Реализовать алгоритм всех возможных комбинаций восьми ферзей

19.05.2016, 05:11. Показов 5703. Ответов 119

Author24 — интернет-сервис помощи студентам
Доброго времени суток! Мне стыдно задавать такой вопрос, но всё же, как реализовать алгоритм всех возможных комбинаций восьми ферзей?

Используйте исчерпывающий «лобовой» подход, т.е. попробуйте все возможные комбинации восьми ферзей на шахматной доске.


Я, думаю, что как-то так: Пройтись по всем строкам и столбцам, выяснить возможно ли поставить ферзей с таких то координат, (0, 0), (0, 1), (0, 2)....(0, 7) , (1, 0) (1, 1) .... ну и так далее до (7, 7) и каждую координату обрабатывать, выясняя, если поставить первого ферзя на на эти коордитаты, то остальные семь ферзей возможно ли разместить на доске. Вот такая вот идея решения) Но решение не могу написать, функция обработки не получается почему-то...
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <iomanip>
//#include "CyrIOS.h"
 
const int hor[8] = {1,1,0,-1,-1,-1,0,1};
const int ver[8] = {0,-1,-1,-1,0,1,1,1};
 
void printBoard(int [][8]);
void resetBoard(int [][8]);
bool checkBoard(int [][8]);
void tryQueen(int [][8], int&, int&);
int helpUpdateBoard(int [][8], int&, int&, bool);
 
using namespace std;
int main()
{
    int board[8][8];
    int cnt = 0;
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
                resetBoard(board);
                tryQueen(board, i, j);
                if(checkBoard(board))
                {
                    printBoard(board);
 
                }
                else
                    continue;
            }
                
        }
        return 0;
}
 
bool checkBoard(int brd[][8])  //проверяем, расставлены ли все восемь ферзей.
{
    int counter = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            if(brd[i][j] == 100)
                counter++;
        }
    }
    return (counter == 8 ? true : false);
}
 
void printBoard(int brd[][8])  //выводим массив
{
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            cout << setw(5) << (brd[i][j] == 100 ? "[]" : ".");
        }
        cout << endl << endl;
    }
}
 
void resetBoard(int brd[][8]) //обнуляем массив
{
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            brd[i][j] = 0;
        }
    }
}
 
void tryQueen(int brd[][8], int& row, int& col)
{
    brd[row][col] = 100; //Постановка первого ферзя
    helpUpdateBoard(brd, row, col, true);
    static int cnt = 0;
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
          if(brd[i][j] != 100 && brd[i][j] != 99)
          {
              brd[i][j] = 100;         //пробуем поставить следующего ферзя
              helpUpdateBoard(brd, i, j, true);  //убиваем клетки которые ферзь бъёт.
             
          }
        }
    }
}
 
int helpUpdateBoard(int brd[][8], int& row, int& col, bool label)
{
    int currentRow, currentColumn;
    int moveNumber;
    int counter = 0;
    
    currentRow = row;
    currentColumn = col;
    while(currentRow < 7)
    {
        moveNumber = 0;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
            
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow < 7 && currentColumn > 0)
    {
        moveNumber = 1;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentColumn > 0)
    {
        moveNumber = 2;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow > 0 && currentColumn > 0)
    {
        moveNumber = 3;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow > 0)
    {
        moveNumber = 4;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow > 0 && currentColumn < 7)
    {
        moveNumber = 5;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentColumn < 7)
    {
        moveNumber = 6;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
    }
    
    currentRow = row;
    currentColumn = col;
    while(currentRow < 7 && currentColumn < 7)
    {
        moveNumber = 7;
        currentRow += hor[moveNumber];
        currentColumn += ver[moveNumber];
        
        if(label)
            brd[currentRow][currentColumn] = 99;
        if(brd[currentRow][currentColumn] != 100 && brd[currentRow][currentColumn] != 99)
            counter++;
        
    }
    return counter;
}


Я уже несколько дней с этой задачей маюсь, надо всё же понять как решать подобное, не просто скопировать код, а понять как это решать, ну и подобные, соответственно.

Смотрел примеры решения, но не понял код, что, куда, зачем, например
C++
1
2
bool tst(int i, int j, int k) {
    return k==i ? 1 : m[k]!=j && (i-k)!=(j-m[k]) && (i-k)!=(m[k]-j) && tst(i,j,k+1);}
Ясно, что фуркция что-то проверяет и возвращает истину или ложь, но вникнуть не могу в суть функции, если кто может, объясните что к чему).


Попрошу сильно не пинать, форум насколько я понял для начинающих!
Спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.05.2016, 05:11
Ответы с готовыми решениями:

Сортировка всех возможных комбинаций 4 из 8
Задача состоит в том, что бы сложить 4 элемента массива, который состоит из 8 элементов, во всех...

Создание всех возможных комбинаций английского алфавита
Подскажите пожалуйста код для создания всех возможных комбинаций английского алфавита. И чтобы эти...

Перебор всех возможных комбинаций
Доброго дня. Есть задание, написать брутфорс, по заданному алфавиту. То что представлено ниже,...

Генератор всех возможных комбинаций
Нужно написать генератор всех возможных комбинаций, допустим состоящих из 2-х, 3-х, 4-х символов и...

119
_Ivana
19.05.2016, 05:28
  #2

Не по теме:

Только что откинулся после длинного срока, а тут какой-то до боли знакомый кот :D

0
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,538
19.05.2016, 05:37  [ТС] 3
Цитата Сообщение от _Ivana Посмотреть сообщение
Только что откинулся после длинного срока, а тут какой-то до боли знакомый кот
Да, он самый.

Добавлено через 2 минуты
_Ivana
Ты не мог бы как-то его более подробно, точнее, более детально разъяснить, скажим так, разживать
0
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 29
19.05.2016, 05:41 4
Это функция, которая тестирует, можно ли поставить ферзя в заданные координаты, при условии, что на предыдущих столбцах уже стоят ферзи с сохранением инварианта "никто никого не бьет". Да, она на "растяжках" - используется внешний массив уже расставленных фигур до требуемого столбца - m.
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 05:42 5
Цитата Сообщение от _Ivana Посмотреть сообщение
Не по теме:
Только что откинулся после длинного срока, а тут какой-то до боли знакомый кот
Да-да, узнаю брата Колю! Слушайте, как вы сами в своем коде что-то понимаете? Ну ладно, сразу после написания, а спустя время понимаете что-нибудь?
0
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 29
19.05.2016, 05:45 6
Mr.X, ну так я далеко не каждого кота пишу с целью понять его после долгой отсидки Элемент некоей намеренной обфускации (но не в ущерб краткости) также имеет место быть. О мотивах - разговор отдельный. И, как видите, я таки вспомнил и понял былого кота
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 05:49 7
Цитата Сообщение от _Ivana Посмотреть сообщение
после долгой отсидки
А где вы были-то?
0
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 29
19.05.2016, 05:51 8
Цитата Сообщение от Mr.X Посмотреть сообщение
А где вы были-то?
Страдал за озвучивание правды и собственного мнения на этом демократическом свободном форуме.
ЗЫ есть все шансы, что следующей мерой будет виртуальный расстрел.
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 05:57 9
Ну, я тут наверно уже все задачи перерешал, про ферзей точно где-то есть, хотел сейчас найти, и обнаружил, что расширенный поиск не работает! Вообще! Никакие мои сообщения не находит! Кто-нибудь знает с чем это связано?
0
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 29
19.05.2016, 05:59 10
Mr.X, в правом верхнем углу есть ссылка "темы с моими ответами" - у меня работает, да и поиск вроде тоже.
ЗЫ: А 8 ферзей "уже в каждой аптеке есть" (С)
0
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,538
19.05.2016, 06:02  [ТС] 11
Цитата Сообщение от _Ivana Посмотреть сообщение
Да, она на "растяжках"
Что за растяжки

То что она проверяет я понял, не понял зачем параметр K, он вызывается рекурсивно для чего, чтобы условие стало истинным?
Код
 i == k
Краткость сестра таланта, но видимо не всегда) Проще говоря она проверяет столбец на предмет того, бъет эту клетку какой-то ферзь или нет, так... Вычитание строк, столбцов эти манипуляции маня и напрягли, всё для того, чтобы условие стало истинным, если
C++
1
k == i
возвращаем 1 , иначе совершаем все эти магические манипуляции с параметрами и, если условие истинно, то возвращаем истину, короче я совсем запуталя. Смотрел в отладчике, там индекс I был равен 5 , а индекс K = 0 и он увеличивался, но не до 5, как у I, а до 3, а затем сново уменьшился до 0 - это работа рекурсии насколько я понял)
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 06:06 12
Цитата Сообщение от _Ivana Посмотреть сообщение
Mr.X, в правом верхнем углу есть ссылка "темы с моими ответами" - у меня работает, да и поиск вроде тоже.
Там только с сентября прошлого года. Я раньше писал, по-моему. Поиск по ключевым словам в моих сообщениях вообще ничего не находит.
0
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,538
19.05.2016, 06:06  [ТС] 13
Рассуждения хоть верны о ходе решения поставленной задачи. За какую правду страдал, если не секрет, чтобы местные Силовые структуры не узнали)
0
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 29
19.05.2016, 06:08 14
"Растяжки" - это на нашем зоновском жаргоне - это глобальные мутабельные переменные, доступные из любого места кода Грязно, но для краткости сойдет. Можно было бы на лямбдах написать, с локальными растяжками, но понятнее от этого бы не стало - поверьте А так вы на правильном пути честного реверс-инжиниринга - смотрите в отладчике содержимое растяжки m и что возвращает функция при разных аргументах.
0
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,538
19.05.2016, 06:09  [ТС] 15
Вы о чём вообще, давно не видились что ли...
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 06:12 16
Цитата Сообщение от Liss29 Посмотреть сообщение
Мне стыдно задавать такой вопрос, но всё же, как реализовать алгоритм всех возможных комбинаций восьми ферзей?
Используйте исчерпывающий «лобовой» подход, т.е. попробуйте все возможные комбинации восьми ферзей на шахматной доске.
Элементарно. Упорядочите как-то клетки доски, и начинайте ставить каждого ферзя на самую левую допустимую клетку. Когда очередного ставить уже некуда, начинайте "шевелить" с хвоста. Т.е. передвигаете последнего поставленного на следующую допустимую клетку, а следующих за ним - опять в самую левую допустимую.
0
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,538
19.05.2016, 06:17  [ТС] 17
Цитата Сообщение от _Ivana Посмотреть сообщение
возвращает функция при разных аргументах.
Смотрел, уже глаза болят смотерть в монитор, возвращает либо
C++
1
false
, либо
C++
1
true
...
Из main вызывается только функция f(0); с аргументом 0, меня это первоначально смутило тем, что индекс должен как-то увеличиваться, а у вас всё решается как-то и без этого))) Я пробовал с рекурсией порешать, у меня ошибка переполнения стека только выпрыгивает, так что решил по старинке итеративно, но...
0
4820 / 2286 / 287
Регистрация: 01.03.2013
Сообщений: 5,970
Записей в блоге: 29
19.05.2016, 06:26 18
Liss29, ладно, давайте на чисто ту Этот мой код - не самый простой для понимания новичку решения данной задачи. Но зато у вас есть 4 варианта:
1) думать и писать самому
2) разбираться в деталях моей реализации
3) разобраться в АЛГОРИТМЕ моей реализации (увидеть его в коде), а детали написать самому - ту же функцию проверки расстановки
4) поискать другие примеры реализации

Полная свобода выбора - смотря что вам интереснее
0
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,538
19.05.2016, 06:31  [ТС] 19
Цитата Сообщение от Mr.X Посмотреть сообщение
Элементарно. Упорядочите как-то клетки доски, и начинайте ставить каждого ферзя на самую левую допустимую клетку. Когда очередного ставить уже некуда, начинайте "шевелить" с хвоста. Т.е. передвигаете последнего поставленного на следующую допустимую клетку, а следующих за ним - опять в самую левую допустимую
Хм. Спасибо, попробую только не понятно, первый на (0, 0), следующий как (1, 2), так как на самую левую невозможно его поставить, если первый ферзь уже стоит на (0, 0), но это не совсем то что вы пишете,

Добавлено через 4 минуты
_Ivana
Мне нужно и в вашем коде разобраться, всё же он компактен, по производительность сказать не могу, но тем неменее надо учиться писать так как вы, а не так как я написал.

Думать, я уже сколько думаю, но ничего пока лучшего, чем то, что я выложил не придумал)))

Разобраться и написать самому, я вначале темы так и написал.
0
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 06:39 20
Цитата Сообщение от Liss29 Посмотреть сообщение
следующий как (1, 2)
Да, это и есть на
Цитата Сообщение от Mr.X Посмотреть сообщение
самую левую допустимую клетку
Добавлено через 4 минуты
Цитата Сообщение от Liss29 Посмотреть сообщение
_Ivana
Мне нужно и в вашем коде разобраться, всё же он компактен, по производительность сказать не могу, но тем неменее надо учиться писать так как вы, а не так как я написал.
Это кто вам такое сказал?
_Ivana парень умный, но его код как раз яркий пример того как писать не нужно. Программа должна быть самодокументируемой и понятной. Многие специалисты считают, что это даже важнее быстродействия и экономии памяти.
0
19.05.2016, 06:39
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.05.2016, 06:39
Помогаю со студенческими работами здесь

Генерация всех возможных комбинаций
Доброго времени суток, подскажите идею, нужно чтобы функция составила все возможные комбинации из...

Вывод всех возможных комбинаций
Здравствуйте! Определена строка русским алфавитом, необходимо вывести все возможные комбинации слов...

Выбор всех возможных комбинаций из Списка
Всех приветствую. Я понимаю,что задача очень простая,но всё же посоветуйте пожалуйста наилучший...

Сумма вероятностей всех возможных комбинаций
Здравствуйте. Объясните, пожалуйста. Например, есть три символа, каждому присвоена...

Генератор всех возможных комбинаций строки
Помогите сделать генератор ВСЕХ значений видов: CBCCB BCCBC Где: C - цифры(2-9) B - буквы(A-Z)...

Просчёт всех возможных комбинаций из 6 цифр
Мужики, в общем забыл пароль от телефона(meizu m1 note) перерыл тонны форумов, решения этой...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru