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

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

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

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

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


Я, думаю, что как-то так: Пройтись по всем строкам и столбцам, выяснить возможно ли поставить ферзей с таких то координат, (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
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.05.2016, 05:11
Ответы с готовыми решениями:

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

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

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

119
19.05.2016, 05:28

Не по теме:

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

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

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

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

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

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

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

Разобраться и написать самому, я вначале темы так и написал.
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
19.05.2016, 06:39
Цитата Сообщение от Liss29 Посмотреть сообщение
следующий как (1, 2)
Да, это и есть на
Цитата Сообщение от Mr.X Посмотреть сообщение
самую левую допустимую клетку
Добавлено через 4 минуты
Цитата Сообщение от Liss29 Посмотреть сообщение
_Ivana
Мне нужно и в вашем коде разобраться, всё же он компактен, по производительность сказать не могу, но тем неменее надо учиться писать так как вы, а не так как я написал.
Это кто вам такое сказал?
_Ivana парень умный, но его код как раз яркий пример того как писать не нужно. Программа должна быть самодокументируемой и понятной. Многие специалисты считают, что это даже важнее быстродействия и экономии памяти.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
19.05.2016, 06:39
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&amp;d=1772460536 Одним из. . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru