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

@Liss29 · Регистрация: 18.11.2012

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

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

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

Я, думаю, что как-то так: Пройтись по всем строкам и столбцам, выяснить возможно ли поставить ферзей с таких то координат, (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);}

Ясно, что фуркция что-то проверяет и возвращает истину или ложь, но вникнуть не могу в суть функции, если кто может, объясните что к чему).

Попрошу сильно не пинать, форум насколько я понял для начинающих!
Спасибо!

@Liss29 · 19.05.2016, 23:27 **[ТС]**

Вот этот код не аналогичен коду проверок из функции tst?

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
setQueen(int row, int col)
      {
        for(int x = 0; x < 8; x++)
        {
            ++brd[x][col];
            ++brd[row][x];
            int foo;
             foo = col - row + x;
            if(foo >= 0 && foo < 8)
              ++brd[x][foo];
            foo = col + row - x;  //по горизонтали влево вниз?
             if(foo >= 0 && foo < 8)
              ++brd[x][foo];
        }
        
      }

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
resetQueen(int row, int col)
      {
          for(int x = 0; x < 8; x++)
          {
             --brd[x][col];
             --brd[row][x];
             int foo;
             foo = col - row + x;
             if(foo >= 0 && foo < 8)
               --brd[x][foo];
             foo = col + row - x;
             if(foo >= 0 && foo < 8)
               --brd[x][foo];
          }
      }

@_Ivana · 19.05.2016, 23:37

Очевидно, что нет. Это ваши процедуры, которые ничего не возвращают, а только изменяют глобальную борду, увеличивая/уменьшая счетчики сколько раз какая клетка бьется. Моя tst экологически чистая - ничего не изменяет, просто тестирует (как понятно из ее названия - вот он, самодокументирующийся кот

) и возвращает результат теста.

Добавлено через 2 минуты
ЗЫ попробуйте решить задачку - даны 2 точки с координатами каждой: (i,j) и (x,y). Определить, находятся ли они на одной горизонтали или диагонали (любой). Решите для начала это.

@Liss29 · 19.05.2016, 23:56 **[ТС]**

Сообщение от _Ivana

Но мне не кажется, что у вас полное понимание.

Да, есть такое, вы имеете ввиду, что суть я не уловил, если так, то да, вы, правы суть не могу уловить. Это подобно слову на иностранном, буквы я прочёл, а значение слова не понял)

Сообщение от _Ivana

на пальцах представлять как это работает

К этому и стремлюсь.

Show() вроде бы понятно, выводит значения массива, а перед ними выводи Латинску букву + i т.е. A, B, C, D, E... не понятно почему m[i] + 1 это слегка озадачило, но, думаю, решаемо. Затем вызывает саму себя для следующего столбца, если i у вас столбец. Иначе, если условие не выполнено вывести перевод строки.

Понятно, что tst сама по себе, но она же в связке с другими функциями работает, а те в свою очередь тоже производят рекурсивные вызовы. Странно, но я ещё не понял её досканально, для меня это ещё слово, значение которого я не знаю.

@_Ivana · 20.05.2016, 00:02

Сообщение от Liss29

не понятно почему m[i] + 1 это слегка озадачило, но, думаю, решаемо

потому что вы же сами писали

Сообщение от Liss29

если массив имеет вид, например, 0, 4, 7, 5, 2, 6, 1, 3. то это может означать, что ферзь установлен на столбец 0, строка 0

, а на шахматной доске нумерация внезапно с единицы

То есть show просто выводит на экран очередной найденный вариант расстановки - в полном соответствии с принципами самодокументирующегося кота, несоблюдение которых мне тут вменяли выше

Рекомендую не игнорировать мою тривиальную задачку парой постов выше.

@Liss29 · 20.05.2016, 05:38 **[ТС]**

даны 2 точки с координатами каждой: (i,j) и (x,y). Определить, находятся ли они на одной горизонтали или диагонали (любой)

Не знаю у меня только одна мысль, если сравнить I с X и, в случе, если они равны, то они на одной горизонтале.

Добавлено через 1 час 26 минут

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include "CyrIOS.h"
 
void printPoint(int [][8]);
bool searchCoor(int array[][8], int row, int col, int x, int y);
 
using namespace std;
int main()
{
    int i, j, x, y;
 
    int point[8][8] = {0};
    cout << "Введите координаты первой точки(i, j): ";
    cin >> i >> j;
    point[i][j] = '*';
    cout << "Введите координаты второй точки(x, y): ";
    cin >> x >> y;
    point[x][y] = '#';
    if(searchCoor(point, i, j, x, y))
    {
        cout << endl << "Координаты пересекаются" << endl;
    }
    else
    {
        cout << endl << "Координаты не пересекаются" << endl;
    }
    
    printPoint(point);
    system("Pause");
    return 0;   
}
 
void printPoint(int p[][8])
{
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
        {
            if(p[i][j] == '*' || p[i][j] == '#')
                cout << static_cast<char>(p[i][j]);
            else
                cout << ' ';
        }
        cout << endl << endl;
        
    }
}
 
bool searchCoor(int array[][8], int row, int col, int x, int y)
{
    bool status = false;
    int i = row;
    int j = col;
    while(i < 7)
    {
        i++;
        if(i == x)
        {
            status = true;
            break;
        }
        else
            break;
    }
    
    i = row;
    j = col;
    while(i < 7 && j < 7)
    {
        i++;
        j++;
        if(i && j == x && y)
        {
            status = true;
            break;
        }
    }
    
    i = row;
    j = col;
    while(i < 7 && j > 0)
    {
        i++;
        j--;
        if(i && j == x && y)
        {
            status = true;
            break;
        }
    }
    
    i = row;
    j = col;
    while(i > 0 && j < 7)
    {
        i--;
        j++;
        if(i && j == x && y)
        {
            status = true;
            break;
        }
    }
    
    i = row;
    j = col;
    while(i > 0 && j > 0)
    {
        i--;
        j--;
        if(i && j == x && y)
        {
            status = true;
            break;
        }
    }
    return status;
}

Не знаю подойдёт ли, но работает.

@Mr.X · 20.05.2016, 08:51

Сообщение от _Ivana

То есть show просто выводит на экран очередной найденный вариант расстановки - в полном соответствии с принципами самодокументирующегося кота, несоблюдение которых мне тут вменяли выше

Не, самодокументируемый код - это такой, в котором имена сущностей рассказывают о том чем эти сущности являются и для чего нужны, т.е. являются и комментариями одновременно.

@_Ivana · 20.05.2016, 13:27

Mr.X, да, а 1 = 1 в экстенсиальном смысле

Сообщение от Liss29

Не знаю подойдёт ли

Нет, не подойдет. Оказывается у вас затруднения в этой локальной подзадачке. Тогда продолжаем решать ее. У вас есть 4 целых числа - координаты двух ферзей на условно безразмерной шахматной доске. Напишите функцию, которая определяет, бьют они друг друга или нет (вы же понимаете, что это перефразировка той же задачи). Доска безразмерная, координаты любые, поэтому никакие заполнения квадратных массивов всех клеток которые под боем не прокатят.

ЗЫ

Сообщение от Liss29

Не знаю у меня только одна мысль, если сравнить I с X и, в случе, если они равны, то они на одной горизонтале.

это правильно (если вы настаиваете, что первая координата - строка), теперь думайте как проверить диагонали.

@Liss29 · 20.05.2016, 23:42 **[ТС]**

Сообщение от _Ivana

теперь думайте как проверить диагонали

Она как-то перекликается с вашим кодом, который мы разбирали выше?
Я так понял в том коде, который описывали выше функции f() и loop() это всего лишь реализация алгоритма повторения, цикл проще говоря по стокам и столбцам, ну или столбцам и стокам у вас? Увеличили столбец, проверили, условие не выполнено идём в tst смотрим, если истинно , вызываем рекурсивно tst(i, j, k + 1); и так пока либо условие не выполнится, либо одна из проверок не покажет ложь. И так пока либо не проходим все 8 строк, либо, если прошли все итерации по столбцу, а результата нет, идём на предыдущую строку и вызываем её с увеличенным на один столбцом и так далее. Говорю же, потихоньку ясность насупает

Пошёл думать, может и решу задачку, но диагонали меня как-то настараживают!

Добавлено через 1 час 36 минут

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
bool a(int i, int j, int x, int y)
{
    if(abs(i - x) == abs(j - y)) /*если при вычитании строк разных ферзей и столбцов они равны или смметричны 2;-2, -3;3 .. то возвращаем истину, значит пересекаются, иначе нет.*/
        return true;
    else
        return false;
}

Что-то навеяло)

@_Ivana · 20.05.2016, 23:55

Ну вот, а то 120 строк кода с мучением двумерного массива

Теперь с учетом этого волшебного откровения и всего того, что выяснили ранее, можно еще помедитировать над функцией tst

@Liss29 · 21.05.2016, 03:53 **[ТС]**

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

@_Ivana · 21.05.2016, 04:21

Можете начать с медитаций над другими, совсем тривиальными котами, например Определить, имеется ли среди цифр натурального числа N

@Liss29 · 21.05.2016, 05:45 **[ТС]**

Когда я смотрел в массиве, то было понятно, что если я произвожу некоторые манипуляции с данными, например,

Code
1
i++; j--;

, то это движение по горизонтали вниз влево, а здесь я не могу сориентироваться потому и столь долгие мучения в понимании. m[k] != j по горизонтали, но мне это не очевидно, как это понять, тут без поллитра не разберёшся.

По горизонтали (i - k) - это столбцы, если следовать вашей стратегии, мы их вычитаем и... а это значит (j - m[k]) строка и некое значение в массиве, значит если они равны, то происходит бой фигуры. Если, например условие (i - k) != (j - m[k]) = 3, а условие (i - k) != (m[k] - j) = -3, то оба условия участвуют в проверке или только то, у кого значение положительное, я к чему это спрашиваю, когда писали функции задавили проверки чтобы значение не вышло за пределы массива, соответственно, например, i < 7 && i > 0; а здесь -3 значит оно не участвует в данной проверке или здесь сново всё иначе? Если они всегда симметричны, то это может означать, что они всего лишь ходят по разным диагоналям

Пока не разберусь какое значение за какую диагональ отвечает не пойму алгорит.

Ещё есть такой момент, когда функция удовлетворяет условию j < 8; мы вытасквиваем из стека всё семь значений, которые туда положили, и начинаем ходить с других координат, с предыдущей строки, стольца, так? Но как он понимает какие именно координаты нужны и где это задаётся какие значения нужно выбирать? Первые после тех 7, которые мы только что вытащили?

Добавлено через 7 минут
Я так понял, последовательно число делится на 8 и проверяется на предмет остатка равного 1, если такое присутствует то возвращаем истину иначе ложь!

Добавлено через 52 минуты
Получается, если я захочу проверку проводить и по вертикали, то это будет выглядеть как

C++
1
m[k] != i;

рискну предположить

@_Ivana · 21.05.2016, 06:26

Сообщение от Liss29

Получается, если я захочу проверку проводить и по вертикали,

то это нафиг не надо, т.к. у нас (у меня, m) структура хранения расположения ферзей на доске не позволяет в одну вертикаьь впихнуть более одного ферзя - ну нельзя элементу массива присвоить 2 значения, не получится

Сообщение от Liss29

то это будет выглядеть как

C++
1
k != i

конечно же

@Liss29 · 21.05.2016, 21:42 **[ТС]**

Здесь я имел ввиду чисто гипотетическую ситуацию, если бы я захотел проверить по вертикали, наверное, так надо было написать.

Код, который вы просили описать т.е. поколдовать над ним, как моё описание верно или опять не совсем то)

@Liss29 · 21.05.2016, 22:11 **[ТС]**

А по диагоналям как-то так

@Liss29 · 22.05.2016, 23:23 **[ТС]**

Похоже теоретически я понял, но вот воспроизвести не смог, имею виду, не смог что-то подобное, но именно своё написать.

Добавлено через 24 минуты
_Ivana
Дружище,а если бы я захотел делать проверку подобную той, которая у вас в коде присутствет, но вместо одномерного массива включить двумерный, такой компактный код уже не получается? Я пробовал, но первое как отмечать координаты, подобно тому, как отмечается в одномерном массиве, но так и не дошёл до чего то более менее вразумительного, втрое не понятно, когда при проверке мы просмотрели все строки или столбцы и все позиции оказались бъющимися, мы начинаем делать ход с предыдущей удачной постановки ферзя т.е. с координат на которые он установлен, и соответсвенно проделываем все шаги с этими координатами, если удача и не бъётся, то в одномерном массиве мы просто меняем значение строки(у вас) , а в двумерном массиве как это может выглядеть, не представляю. Я хочу выводить все удачные расстановки, поэтому сразу решил было устанавливать координаты и по этим коордтинатам отмечать, что на этом месте стоит фигура, ну например так, "[]" но возвращаясь к предыдущим строкам, если мы начнём делать проверку со строки с предыдущими координатами, то при удачном стичении обстоятельств, при постановки фигуры на новый столбец этой же строки, становяться две фигуры на одной строке так как предыдущая не затирается, получается полный бред. Поэтому зделал вывод, что в вашей процедуре всё заточено под одномерный массив

Всё вроде бы просто и в тоже время не просто

@_Ivana · 22.05.2016, 23:37

Дело не в одномерном/двумерном массиве и вообще не в структуре данных хранения расстановки - она может быть любой, позволяющей реализовать алгоритм. В алгоритм надо въехать просто

Тут классика - обход графа в глубину (можешь погуглить), то есть например: мы ставим первого ферзя на А1 и перебираем варианты расстановок остальных семи, которые удовлетворяют условию, потом переставляем первого на А2 - и делаем то же самое. Причем, не только для первого ферзя работает эта логика - для любого ферзя мы в цикле ставим его на все клетки поля, где он не бьется и пробуем доставить остальных - если доставили, то выводим результат, если какого-то ферзя никуда нельзя поставить чтобы он не бился - прерываем разбор этой ветки. А в каких структурах данных хранить расстановки - неважно, главное четко уметь "забывать" или "очищать" расстановки последующих ферзей при возврате на уровень выше в рекурсии. И в ситуации с одномерным массивом это делается очень просто (хотя и неявно) - индекс массива помнится свой в каждом уровне рекурсивного вызова (т.к. он является входящим параметром функции).

@Liss29 · 22.05.2016, 23:53 **[ТС]**

Да, кстате, если по условию задачи, то, на сколько я понял, мне нужно найти все возможные варианты расстановки ферезй т.е. начать вызывать с координатами 0, 0 , а закончить 7, 7 . Это моё видение, но если допустим, функциия дошла до координат 7, 7 , то по сути она по условию выхода практически сразу же завершится, так?

Обход графа в глубину посмотрю обязательно. Главное чтобы по проще описано было

обход графа в глубину

По сути это и есть решения моей задачи. Только автор об это почему-то "забыл" упомянуть, про такие примудрости вообще ничего не знаю

@_Ivana · 23.05.2016, 00:02

Только чтобы не было дублирующихся расстановок (одних и тех же по координатам, но отличающихся по "порядковым номерам" ферзей на них), надо следующего ферзя ставить на клетки больше (лексикографически) текущей, поэтому если первый ферзь у вас стоит на 7,7 то остальных ставить некуда

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

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

ЗЗЫ

Сообщение от Liss29

Только автор об это почему-то "забыл" упомянуть

а он и не должен был упоминать. Иначе получится "не найдешь - я в шкафу сижу"

Буквально сейчас в новостях чествуют питерскую команду - победителей чемпионата мира по программированию. Вы думаете у них в задачах в конце были приписки типа "использовать поиск в глубину" или "решать через динамическое программирование - рекурсия с мемоизацией"?

@Liss29 · 23.05.2016, 05:10 **[ТС]**

Сообщение от _Ivana

в новостях чествуют питерскую команду - победителей чемпионата мира по программированию.

Кхе... вы мне,_Ivana, польстили, спасибо, теперь я исполнен важности мне и решать ничего не хочется

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

Сообщение от _Ivana

поэтому если первый ферзь у вас стоит на 7,7 то остальных ставить некуда

А как тогда найти все возможные комбинации 8 ферзей на доске... Ещё не лучше теперь я даже не знаю с чего начать

Просто хотел выводить как обычно что-то похожее на доску с метками, которые, условно, обозначают ферзей, до красоты мне ещё далеко я так пологаю.

Сообщение от _Ivana

рекурсия с мемоизацией"?

Какие-то вы загадочные заклинания произносите, даже не по себе стало.

Значит ваш алгоритм и есть тот самый поиск в глубину. Вместо цикла, скажем, for вы создали свой из двух функций. Если это так, то значит я врубился в алгоритм, тогда что, функция проверки вроде тоже понятна, не понял или точнее не совсем допонял, как эти диагональные движения происходят, а так ясно. Если я так буду делать (j - k) != (i - m[k]) чтобы понятней было мне i - строка, j - столбец всё будет дастишь фантастишь

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

вот какая идея меня посетила с просони

Кликните здесь для просмотра всего текста

C++
1
k == i ? 1 : board[k][j] != i && (j - k) != (i - borad[k][k]) && (j - k) != (board[k][k] - i) && tst(i, j, k + 1);

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	19.05.2016, 23:37
	Очевидно, что нет. Это ваши процедуры, которые ничего не возвращают, а только изменяют глобальную борду, увеличивая/уменьшая счетчики сколько раз какая клетка бьется. Моя tst экологически чистая - ничего не изменяет, просто тестирует (как понятно из ее названия - вот он, самодокументирующийся кот ) и возвращает результат теста. Добавлено через 2 минуты ЗЫ попробуйте решить задачку - даны 2 точки с координатами каждой: (i,j) и (x,y). Определить, находятся ли они на одной горизонтали или диагонали (любой). Решите для начала это. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	20.05.2016, 23:55
	Ну вот, а то 120 строк кода с мучением двумерного массива Теперь с учетом этого волшебного откровения и всего того, что выяснили ранее, можно еще помедитировать над функцией tst 0

@Liss29 225 / 39 / 4 Регистрация: 18.11.2012 Сообщений: 1,633
	21.05.2016, 03:53 [ТС]
	Я уже долго с ней медетирую, но даже с учётом открывшегося мне откровения ясности мало. Так что можно и помедитировать 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	21.05.2016, 04:21
	Можете начать с медитаций над другими, совсем тривиальными котами, например Определить, имеется ли среди цифр натурального числа N 0

@Liss29 225 / 39 / 4 Регистрация: 18.11.2012 Сообщений: 1,633
	21.05.2016, 21:42 [ТС]
	Здесь я имел ввиду чисто гипотетическую ситуацию, если бы я захотел проверить по вертикали, наверное, так надо было написать. Код, который вы просили описать т.е. поколдовать над ним, как моё описание верно или опять не совсем то) 0

@Liss29 225 / 39 / 4 Регистрация: 18.11.2012 Сообщений: 1,633
	21.05.2016, 22:11 [ТС]
	А по диагоналям как-то так Миниатюры 0

@Liss29 225 / 39 / 4 Регистрация: 18.11.2012 Сообщений: 1,633
	22.05.2016, 23:23 [ТС]
	Похоже теоретически я понял, но вот воспроизвести не смог, имею виду, не смог что-то подобное, но именно своё написать. Добавлено через 24 минуты _Ivana Дружище,а если бы я захотел делать проверку подобную той, которая у вас в коде присутствет, но вместо одномерного массива включить двумерный, такой компактный код уже не получается? Я пробовал, но первое как отмечать координаты, подобно тому, как отмечается в одномерном массиве, но так и не дошёл до чего то более менее вразумительного, втрое не понятно, когда при проверке мы просмотрели все строки или столбцы и все позиции оказались бъющимися, мы начинаем делать ход с предыдущей удачной постановки ферзя т.е. с координат на которые он установлен, и соответсвенно проделываем все шаги с этими координатами, если удача и не бъётся, то в одномерном массиве мы просто меняем значение строки(у вас) , а в двумерном массиве как это может выглядеть, не представляю. Я хочу выводить все удачные расстановки, поэтому сразу решил было устанавливать координаты и по этим коордтинатам отмечать, что на этом месте стоит фигура, ну например так, "[]" но возвращаясь к предыдущим строкам, если мы начнём делать проверку со строки с предыдущими координатами, то при удачном стичении обстоятельств, при постановки фигуры на новый столбец этой же строки, становяться две фигуры на одной строке так как предыдущая не затирается, получается полный бред. Поэтому зделал вывод, что в вашей процедуре всё заточено под одномерный массив Всё вроде бы просто и в тоже время не просто 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	22.05.2016, 23:37
	Дело не в одномерном/двумерном массиве и вообще не в структуре данных хранения расстановки - она может быть любой, позволяющей реализовать алгоритм. В алгоритм надо въехать просто Тут классика - обход графа в глубину (можешь погуглить), то есть например: мы ставим первого ферзя на А1 и перебираем варианты расстановок остальных семи, которые удовлетворяют условию, потом переставляем первого на А2 - и делаем то же самое. Причем, не только для первого ферзя работает эта логика - для любого ферзя мы в цикле ставим его на все клетки поля, где он не бьется и пробуем доставить остальных - если доставили, то выводим результат, если какого-то ферзя никуда нельзя поставить чтобы он не бился - прерываем разбор этой ветки. А в каких структурах данных хранить расстановки - неважно, главное четко уметь "забывать" или "очищать" расстановки последующих ферзей при возврате на уровень выше в рекурсии. И в ситуации с одномерным массивом это делается очень просто (хотя и неявно) - индекс массива помнится свой в каждом уровне рекурсивного вызова (т.к. он является входящим параметром функции). 0