Задача о 8 ферзях: сколько было сделано возвратов назад

@Дмиттрий · Регистрация: 03.12.2015

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

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

Условие задачи: В программе о восьми ферзях (рекурсивной) подсчитайте, сколько было сделано возвратов назад.
Я так понял, что нужно подсчитать сколько раз не удалось поставить ферзя)

Буду очень признателен, за помощь.
Заранее спасибо.

Данный код подсчитывает все возможные варианты.

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
#include <iostream>
using namespace std;
const int N= 8; // Размер.
int board[N][N];
int results_count = 0; // Количество решений.
    
int main()
{
    setQueen(0);
    return 0;
}
 
void showBoard()   // Функция showBoard() - отображает доску.
{
    for (int a = 0; a < N; ++a)
    {
        for (int b = 0; b <N; ++b)
        {
            cout << ((board[a][b]) ? "Q " : ". ");
        }
        cout << '\n';
    }
}
 
// Функция tryQueen() - проверяет нет ли уже установленных ферзей,
// по вертикали, диагоналям.
bool tryQueen(int a, int b)
{
    for (int i = 0; i < a; ++i)
    {
        if (board[i][b])
        {
            return false;
        }
    }
 
    for (int i = 1; i <= a && b - i >= 0; ++i)
    {
        if (board[a - i][b - i])
        {
            return false;
        }
    }
 
    for (int i = 1; i <= a && b + i < N; i++)
    {
        if (board[a - i][b + i])
        {
            return false;
        }
    }
 
    return true;
}
 
// Функция setQueen() - пробует найти результаты решений.
void setQueen(int a) // a - номер очередной строки в которую нужно поставить очередного ферзя.
{
    setlocale(LC_ALL, "RUS");
    if (a == N)
    {
        //showBoard();
        cout << "Результат" << ++results_count << "\n\n";
        return; // Опционально.
    }
 
    for (int i = 0; i < N; ++i)
    {
        // Здесь проверяем, что если поставим в board[a][i] ферзя (единицу),
        // то он будет единственным в этой строке, столбце и диагоналях.
        if (tryQueen(a, i))
        {
            board[a][i] = 1;
            setQueen(a + 1);
            board[a][i] = 0;
        }
    }
 
    return; // Опционально.
}

@obivan · 06.05.2017, 17:54

скорее всего (если функция tryQueen проверяет можно ли его поставить) в строке 71 где у вас условые с проверкой дописать
else в котором считать кол-во неудачных постановок

@Дмиттрий · 06.05.2017, 18:08 **[ТС]**

Напишите, пожалуйста, как прописать условие, если не трудно кодом

@GoldenId · 06.05.2017, 18:36

C++
1
2
3
4
5
6
7
int main()
{
    int fails = 0;
    setQueen(0, fails);
    cout << "There were :" << fails << " fails" << endl;
    return 0;
}

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
// Функция setQueen() - пробует найти результаты решений.
void setQueen(int a, int& fails) // a - номер очередной строки в которую нужно поставить очередного ферзя.
{
    setlocale(LC_ALL, "RUS");
    if (a == N)
    {
        //showBoard();
        cout << "Результат" << ++results_count << "\n\n";
        return; // Опционально.
    }
 
    for (int i = 0; i < N; ++i)
    {
        // Здесь проверяем, что если поставим в board[a][i] ферзя (единицу),
        // то он будет единственным в этой строке, столбце и диагоналях.
        if (tryQueen(a, i))
        {
            board[a][i] = 1;
            setQueen(a + 1);
            board[a][i] = 0;
        }
        else
           fails++;
    }
 
    return; // Опционально.
}

@Дмиттрий · 06.05.2017, 19:51 **[ТС]**

Пишет ошибку

C++
1
2
3
4
5
6
7
8
if (tryQueen(a, i))
        {
            board[a][i] = 1;
            setQueen(a +1 ); //  вот здесь ошибка (слишком мало аргументов при вызове функции, функция не принимает 1 агрумента 
            board[a][i] = 0;
        }
        else
            fails++;

@GoldenId · 07.05.2017, 10:10

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
    for (int i = 0; i < N; ++i)
    {
        // Здесь проверяем, что если поставим в board[a][i] ферзя (единицу),
        // то он будет единственным в этой строке, столбце и диагоналях.
        if (tryQueen(a, i))
        {
            board[a][i] = 1;
            setQueen(a + 1, fails);
            board[a][i] = 0;
        }
        else
           fails++;
    }

@Дмиттрий · 07.05.2017, 12:13 **[ТС]**

А можно ли переделать эту программу, чтобы он выдавал не 92 варианта, а один.?

@GoldenId · 07.05.2017, 14:30

Можно

@Дмиттрий · 07.05.2017, 16:21 **[ТС]**

Как это можно реализовать ?

@Antikl · 07.05.2017, 16:45

пример о 8 ферзях

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
#include <iostream>
using namespace std;
 
int board[8][8];
 
void setQueen(int i, int j)
{
  for (int x = 0; x < 8; ++x)
  {
    ++board[x][j];
    ++board[i][x];
    int foo;
    foo = j - i + x;
    if (foo >= 0 && foo < 8)
      ++board[x][foo];
    foo = j + i - x;
    if (foo >= 0 && foo < 8)
      ++board[x][foo];
  }
  board[i][j] = -1;
}
 
void resetQueen(int i, int j)
{
  for (int x = 0; x < 8; ++x)
  {
    --board[x][j];
    --board[i][x];
    int foo;
    foo = j - i + x;
    if (foo >= 0 && foo < 8)
      --board[x][foo];
    foo = j + i - x;
    if (foo >= 0 && foo < 8)
      --board[x][foo];
  }
  board[i][j] = 0;
}
 
bool tryQueen(int i)
{
  bool result = false;
  for (int j = 0; j < 8; ++j)
  {
    if (board[i][j] == 0)
    {
      setQueen(i, j);
      if (i == 7)
    result = true;
      else
      {
    if (!(result = tryQueen(i + 1)))
      resetQueen(i, j);
      }
    }
    if (result)
      break;
  }
  return result;
}
 
int main()
{
  for (int i = 0; i < 8; ++i)
    for (int j = 0; j < 8; ++j)
      board[i][j] = 0;
  tryQueen(0);
  for (int i = 0; i < 8; ++i)
  {
    for (int j = 0; j < 8; ++j)
    {
      if (board[i][j] == -1)
    cout << "[]";
      else
    cout << ". ";
    }
    cout << endl;
  }
  system("pause");
  return 0;
}

@GoldenId · 07.05.2017, 17:13

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
#include <iostream>
using namespace std;
const int N= 8;         // Размер.
int board[N][N];
int results_count = 0;  // Количество решений.
int fails;              // Количество неудач
 
// a - номер очередной строки в которую нужно поставить очередного ферзя.
bool setQueen(int a);
// Функция showBoard() - отображает доску.
void showBoard();
// Функция tryQueen() - проверяет нет ли уже установленных ферзей,
// по вертикали, диагоналям.
bool tryQueen(int a, int b);
 
 
int main()
{
    setQueen(0);
    cout << "There were :" << fails << " fails" << endl;
}
 
void showBoard()   // Функция showBoard() - отображает доску.
{
    for (int a = 0; a < N; ++a)
    {
        for (int b = 0; b <N; ++b)
        {
            cout << ((board[a][b]) ? "Q " : ". ");
        }
        cout << '\n';
    }
}
 
// Функция tryQueen() - проверяет нет ли уже установленных ферзей,
// по вертикали, диагоналям.
bool tryQueen(int a, int b)
{
    for (int i = 0; i < a; ++i)
    {
        if (board[i][b])
        {
            return false;
        }
    }
 
    for (int i = 1; i <= a && b - i >= 0; ++i)
    {
        if (board[a - i][b - i])
        {
            return false;
        }
    }
 
    for (int i = 1; i <= a && b + i < N; i++)
    {
        if (board[a - i][b + i])
        {
            return false;
        }
    }
 
    return true;
}
 
// Функция setQueen() - пробует найти результаты решений.
bool setQueen(int a) // a - номер очередной строки в которую нужно поставить очередного ферзя.
{
    setlocale(LC_ALL, "RUS");
    if (a == N)
    {
        //showBoard();
        cout << "Результат" << ++results_count << "\n\n";
        return true; // Опционально.
    }
 
    for (int i = 0; i < N; ++i)
    {
        // Здесь проверяем, что если поставим в board[a][i] ферзя (единицу),
        // то он будет единственным в этой строке, столбце и диагоналях.
        if (tryQueen(a, i))
        {
            board[a][i] = 1;
            if (setQueen(a + 1))
                return true;
            board[a][i] = 0;
        }
        else
           fails++;
    }
 
    return false; 
}

@Дмиттрий · 07.05.2017, 17:37 **[ТС]**

Но разве может быть такое большое число возвратов. В данном коде получается 763, даже если пробовать поставить каждого ферзя, в каждую клетку максимум 512 возвратов должно быть. А того и того меньше, потому что при установке 1 ферзя их вообще не будет

@GoldenId · 07.05.2017, 19:37

Что Вы понимаете под возвратами?

@Дмиттрий · 07.05.2017, 19:49 **[ТС]**

Сколько раз не удастся поставить ферзя на доску.
То есть, если стоит ферзь, или поле пробиваемо мы получаем 1 возврат

Можнт, я не правильно понимаю условие задачи , условие я размещаю выше

@GoldenId · 07.05.2017, 21:02

Сообщение от Дмиттрий

То есть, если стоит ферзь, или поле пробиваемо мы получаем 1 возврат

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

@Дмиттрий · 10.05.2017, 23:52 **[ТС]**

Подскажи, пожалуйста, пробовал реализовать, как ты сказал ничего не получается. Как это сделать

@GoldenId · 11.05.2017, 00:11

Я описал, как сделано у меня.

@Дмиттрий · 11.05.2017, 00:13 **[ТС]**

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

@_Ivana · 11.05.2017, 00:53

C++
1
2
3
4
5
6
7
8
9
10
11
int m[8], c=0, g=0; void f(int i);
 
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);}
 
void loop(int i, int j) {
    if (j<8 && g==0) {if (tst(i,j,0)) {m[i]=j; f(i+1);} loop(i,j+1);} else c++;}
 
void f(int i) {if (i==8) {cout<<"returns = "<<c<<'\n'; g=1;} else loop(i,0);}
 
int main() {f(0);}

@Дмиттрий · 11.05.2017, 00:57 **[ТС]**

Как добавить в тот код это условие. Мне просто нужно, чтобы сначала были расставлены ферзи и сразу выдавалось количество возвратов.

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@obivan Падаван С++ 447 / 261 / 89 Регистрация: 11.11.2014 Сообщений: 916
	06.05.2017, 17:54
	скорее всего (если функция tryQueen проверяет можно ли его поставить) в строке 71 где у вас условые с проверкой дописать else в котором считать кол-во неудачных постановок 0

@Дмиттрий 0 / 0 / 0 Регистрация: 03.12.2015 Сообщений: 55
	06.05.2017, 18:08 [ТС]
	Напишите, пожалуйста, как прописать условие, если не трудно кодом 0

@Дмиттрий 0 / 0 / 0 Регистрация: 03.12.2015 Сообщений: 55
	07.05.2017, 12:13 [ТС]
	А можно ли переделать эту программу, чтобы он выдавал не 92 варианта, а один.? 0

@GoldenId 142 / 143 / 64 Регистрация: 11.11.2010 Сообщений: 877 Записей в блоге: 10
	07.05.2017, 14:30
	Можно 0

@Дмиттрий 0 / 0 / 0 Регистрация: 03.12.2015 Сообщений: 55
	07.05.2017, 16:21 [ТС]
	Как это можно реализовать ? 0

@Дмиттрий 0 / 0 / 0 Регистрация: 03.12.2015 Сообщений: 55
	07.05.2017, 17:37 [ТС]
	Но разве может быть такое большое число возвратов. В данном коде получается 763, даже если пробовать поставить каждого ферзя, в каждую клетку максимум 512 возвратов должно быть. А того и того меньше, потому что при установке 1 ферзя их вообще не будет 0

@GoldenId 142 / 143 / 64 Регистрация: 11.11.2010 Сообщений: 877 Записей в блоге: 10
	07.05.2017, 19:37
	Что Вы понимаете под возвратами? 0

@Дмиттрий 0 / 0 / 0 Регистрация: 03.12.2015 Сообщений: 55
	07.05.2017, 19:49 [ТС]
	Сколько раз не удастся поставить ферзя на доску. То есть, если стоит ферзь, или поле пробиваемо мы получаем 1 возврат Можнт, я не правильно понимаю условие задачи , условие я размещаю выше 0

@Дмиттрий 0 / 0 / 0 Регистрация: 03.12.2015 Сообщений: 55
	10.05.2017, 23:52 [ТС]
	Подскажи, пожалуйста, пробовал реализовать, как ты сказал ничего не получается. Как это сделать 0

@GoldenId 142 / 143 / 64 Регистрация: 11.11.2010 Сообщений: 877 Записей в блоге: 10
	11.05.2017, 00:11
	Я описал, как сделано у меня. 0

@Дмиттрий 0 / 0 / 0 Регистрация: 03.12.2015 Сообщений: 55
	11.05.2017, 00:13 [ТС]
	"Но это не возврат. Возврат осуществляется, когда проходится строка и в ней не обнаруживается возможности поставить очередного ферзя." - Я так пробовал 0

@Дмиттрий 0 / 0 / 0 Регистрация: 03.12.2015 Сообщений: 55
	11.05.2017, 00:57 [ТС]
	Как добавить в тот код это условие. Мне просто нужно, чтобы сначала были расставлены ферзи и сразу выдавалось количество возвратов. 0