Форум программистов, компьютерный форум CyberForum.ru

Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
Icewinder
1 / 1 / 0
Регистрация: 30.09.2012
Сообщений: 31
09.12.2012, 15:25     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #1
Нужно написать программу которая расставляет на шахматной доске 8 ферзей, которые не бьют друг друга.
обязательно использование рекурсии, ну и struct .
Извините если такая тема была, интернет 64кбитный.
Спасибо =)

Добавлено через 2 часа 5 минут
Ап темы

Добавлено через 2 часа 0 минут
ап темы
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2012, 15:25     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга
Посмотрите здесь:

Расставить 8 Ферзей на шахмотной доске... в борланд С C++
Рекурсивный алоритм шахматная доска расставить фигуры так чтобы не били друг друга C++
C++ Сколько коней можно без угроз друг другу расставить на шахматной доске размером M на N
C++ На шахматной доске стоят три ферзя. найти ту пару из них которые угрожают друг другу!
C++ Расставить n ладей на шахматной доске n*n
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
09.12.2012, 15:27     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #2
рекурсией
я прочитал впервые о решении в книжке Окулова.
Icewinder
1 / 1 / 0
Регистрация: 30.09.2012
Сообщений: 31
09.12.2012, 15:32  [ТС]     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #3
А что за книга?Программирование в алгоритмах? или основы программирования?

Добавлено через 2 минуты
Да и тем более там паскаль, ну и обычный с, а плюсов нет
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
09.12.2012, 16:47     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #4
Да, Программирование в алгоритмах!
Ща попробую на С++ показать

Добавлено через 20 минут
Немного переумничал с классами, но думаю и так сойдёт
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 <cstdio>
#include <cstring>
const int size=8;
class board{
protected:
    int rows[size];
    bool columns[size];
    bool Adiags[size*2-1];
    bool Bdiags[size*2-1];
    
 
    void reset(){
        memset(rows, -1, size*sizeof(int));
        memset(columns, false, (size)*sizeof(bool));
        memset(Adiags, false, (size*2-1)*sizeof(bool));
        memset(Bdiags, false, (size*2-1)*sizeof(bool)); 
    }
    bool putQueen(int x, int y){
        if (x<0 || x>=size || y<0 || y>=size ) return false;
        if (rows[y]!=-1) return false;
        if (columns[x]) return false;
        if (Adiags[x+y]) return false;
        if (Bdiags[size+x-y-1]) return false;
 
        rows[y]=x;
        columns[x]=true;
        Adiags[x+y]=true;
        Bdiags[size+x-y-1]=true;
        return true;
    }
    bool removeQueen(int y){
        if (y<0 || y>=size ) return false;
        if (rows[y]==-1) return false;
        int x=rows[y];
        columns[x]=false;
        Adiags[x+y]=false;
        Bdiags[size+x-y-1]=false;
        rows[y]=-1;
        return true;
    }
    bool FindFirstSolve(int i=0){
        for (int j=0; j<8; j++){
            if (putQueen(j, i)){
                if (i==7) 
                    return true;
                if (FindFirstSolve(i+1)) 
                    return true;
                removeQueen(i);
            }
        }
        return false;
    }
    void output(){
        for (int i=0; i<size; i++){
            for (int j=0; j<size; j++)
                if (j==rows[i])
                    putchar('Q');
                else
                    putchar('.');
 
            putchar('\n');
        }
    }
public:
    board(){}   
    void run(){
        int i=0;
        reset();
        if (FindFirstSolve())output();
        else printf("megafailure\n");
    }   
 
 
};
 
int main(){
    board Chessboard;
    Chessboard.run();
    getchar();
    return 0;
}
Icewinder
1 / 1 / 0
Регистрация: 30.09.2012
Сообщений: 31
09.12.2012, 17:04  [ТС]     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #5
Большое спасибо, добрый человек. Вроде разобрался
System16v
 Аватар для System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 16:59     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #6
Ребят,ну подскажите пожалуйста по коду.В книге Дейтела дошел жо этой задачи.Начал писать код насколько понял задачу.Сначала была загвоздка при установке ходов по диагонали(не мог правильно границы массива обозначить),но потом увидел условие в инете,и понял как это сделать. Пытался сделать через рандомные координаты.Программа запускается,НО,не знаю в чем косяк ,если программа, я так понимаю с 3-5 попыток не получает результат,то она попросту виснет наверное(сколько времени не ждал,ничего не изменилось),или цикл зацикливается.Не могу понять почему. Вот код,пояснения написал,может я условие обнуления массива неправильно как-то задал?Ума не приложу где косяк,из-за чего он виснет.Пытался условие обнуления и так и этак менять,все равно зависает,если не получилось сразу . Подскажите пожалуйста начинающему . В данном примере цикл вайл стоит не равным 7ми,т.е. установка 7 ферзей делается.Если поставить для 8ми ферзей,ни разу не получалось увидеть результат.Но видел результат когда выдавал ответ для 7ми ферзей и было 1 пустое место как раз для 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
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
#include <iostream>
#include <vcl.h>
#include <iomanip>
#include <cstdlib>
#include <string>
 
using namespace std;
 
int main()
{
  const int size=8;
  char array[size][size]={0};
  int x,y,c=0,z=0,t=0,e=0;
  srand(time(0));
 
 
 
  for(int i=0;i<size;i++)    // замена всех элементов массива на "-"
     for(int j=0;j<size;j++)
        array[i][j]='-';
  // координаты начальные
  x=0;
  y=0;
  // установка доступных ходов ферзя меняем на "*"
  for(int i=0;i<size;i++)
  {
     array[x][i]='*';
     array[i][y]='*';
  }
  for(int i=0;i<size;i++)
  {
   int k=0;
   k=y-i+x;
   if(k>=0&&k<size)
      array[i][k]='*';
   k=y+i-x;
   if(k>=0&&k<size)
      array[i][k]='*';
  }
  array[x][y]='f';    // меняем символ координаты на символ ферзя
 
  while(z!=7) // установка остальных ферзей
  {
  // если на последнем проходе цикл не завершился,
  // или кол-во доступных ходов равно 0
  // обнуляем массив и устанавливаем заново 1го ферзя в точку 0 0,
    if(t==6||c==0)
    {
      for(int i=0;i<size;i++)
         for(int j=0;j<size;j++)
            array[i][j]=='-';
      x=0;
      y=0;
      for(int i=0;i<size;i++)
      {
       array[x][i]='*';
       array[i][y]='*';
      }
      for(int i=0;i<size;i++)
      {
       int k=0;
       k=y-i+x;
       if(k>=0&&k<size)
          array[i][k]='*';
       k=y+i-x;
       if(k>=0&&k<size)
          array[i][k]='*';
      }
      array[x][y]='f';
      t=0;               // сбрасываем счетчик проходов заново в 0
      e++;               // количество сделанных сбросов
      }
    // выбираем рандомные координаты
    x=rand()%7+1;
    y=rand()%7+1;
     // если по кординатам у нас "*" или "-",пропускаем остальной цикл
     // и выбираем опять рандомные координаты
    if(array[x][y]=='*'||array[x][y]=='f')
       continue;
    for(int i=0;i<size;i++)
    // если координата пуста, то ставим ферзя и рисуем его ходы
    {
     array[x][i]='*';
     array[i][y]='*';
    }
    for(int i=0;i<size;i++)
    {
     int k=0;
     k=y-i+x;
     if(k>=0&&k<size)
        array[i][k]='*';
     k=y+i-x;
     if(k>=0&&k<size)
        array[i][k]='*';
    }
    array[x][y]='f';  // на месте координаты новой,ставил символ ферзя
    c=0;z=0;          // обнуляем счетчик пустых символов и количество ферзей
    for(int i=0;i<size;i++)
    {
       for(int j=0;j<size;j++)
          {
          if(array[i][j]=='-')
             c++;              // считаем кол-во пустых символов
          if(array[i][j]=='f')
             z++;             // считаем кол-во ферзей
          }
    }
    t++;                   // прибавляем к счетчику проходов единицу
 }
 
 
 
  cout << "  0" << " 1" << " 2" << " 3" << " 4" << " 5"
       << " 6" << " 7 " << endl;
  for(int i=0;i<size;i++)
  {
  cout << i << " ";
  for(int j=0;j<size;j++)
        cout << array[i][j] << " ";
  cout << endl;
  }
  cout << "\n\nPustie simvoli = "<<c<<endl;
  cout << "Kolichesto hodov - "<< t+1
       << "\nObnylali massiv = " << e << " raz(a) " << endl;
  cout <<endl;
  system("pause");
  return 0;
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
08.04.2015, 17:25     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #7
System16v, код дикая ересь. Мало того что сама попытка перебора неоптимальна. Так ещё в ней какой-то рандом используется. Поясни, ты надеешься, что рандомно ззаполняя доску ферзями, ты рано или поздно получишь решение? Программисты никогда на такое не надеются.
System16v
 Аватар для System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 17:25     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #8
Вот например добавил,чтоб если после завершения цикла остался пустой символ,заменить его на ферзя(знак доллара взял).У меня такое ощущение что while зацикливается....вот только почему??Сколько раз ни запускал,не видел,чтоб количество обнулений массива при поиске решения было бы больше 0 или больше 1,оно почему то всегда равно единице...как буд-то всегда хоть раз, но массив в цикле обнуляется.А в следующий раз когда нужно обнулить уже не обнуляет из-за чего похоже виснет на рандомных координатах и continue
Миниатюры
Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга  
System16v
 Аватар для System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 17:27     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #9
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
ты рано или поздно получишь решение?
Ну типа того,что рано или поздно он должен найти решение.Рандом используется только для выбора произвольных координат,если место в массиве после выбора координат занято,то выбирается заново рандомная координата.Просто как ни пытался понять,как подобрать координаты рандомно,но по очереди перебирая все варианты - получалась какая-та ерунда. Так а циклится он от чего?
marat_miaki
97 / 86 / 31
Регистрация: 08.04.2013
Сообщений: 297
08.04.2015, 17:27     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #10
самый лучший на вики
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
// Backtracking method. "Поиск с возвратом" на примере
// задачи о восьми ферзях.
 
#include <iostream>
 
const int SIZE = 8; // Размер.
 
int board[SIZE][SIZE];
int results_count = 0; // Количество решений.
 
// Функция showBoard() - отображает доску.
void showBoard()
{
    for(int a = 0; a < SIZE; ++a)
    {
        for(int b = 0; b < SIZE; ++b)
        {
            std::cout << ((board[a][b]) ? "Q " : ". ");
        }
        std::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 < SIZE; i++)
    {
        if(board[a-i][b+i])
        {
            return false;
        }
    }
 
    return true;
}
 
// Функция setQueen() - пробует найти результаты решений.
void setQueen(int a) // a - номер очередной строки в которую нужно поставить очередного ферзя.
{
    if(a == SIZE)
    {
        showBoard();
        std::cout << "Result #" << ++results_count << "\n\n";
        return; // Опционально.
    }
 
    for(int i = 0; i < SIZE; ++i)
    {
        // Здесь проверяем, что если поставим в board[a][i] ферзя (единицу),
        // то он будет единственным в этой строке, столбце и диагоналях.
        if(tryQueen(a, i))
        {
            board[a][i] = 1;
            setQueen(a+1);
            board[a][i] = 0;
        }
    }
 
    return; // Опционально.
}
 
int main()
{
    setQueen(0);
 
    return 0;
}
System16v
 Аватар для System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 17:35     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #11
Да готовый код я видел,мне просто интересно понять где ошибка в моем коде и почему цикл зацикливается периодически .Пытаюсь разобраться просто в последовательности ходов какие делаются по циклам,и не нахожу тот случай там, при котором бы зацикливался цикл.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
08.04.2015, 18:38     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #12
marat_miaki, ничего хорошего в этом варианте не вижу. Г**но какое-то.
marat_miaki
97 / 86 / 31
Регистрация: 08.04.2013
Сообщений: 297
08.04.2015, 18:40     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #13
Ну да только это Г**но все 92 варианта выдает
System16v
 Аватар для System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 18:48     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #14
Ну а мой код выдает 1 правильный результат,вот если бы еще с 1го раза ....было бы вообще отлично
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2016, 23:27     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга
Еще ссылки по теме:

C++ Определить бъют ли две фигуры на шахматной доске друг друга
C++ Используя стандартные правила шахматной игры, определить бьют фигуры друг друга или нет
На шахматной доске отметить все клетки, которые бьет слон C++

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

Или воспользуйтесь поиском по форуму:
Liss29
 Аватар для Liss29
20 / 9 / 2
Регистрация: 18.11.2012
Сообщений: 402
Завершенные тесты: 1
13.05.2016, 23:27     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга #15
( Восемь ферзей: методы решения «в лоб») В этом упражнении вы будете разви*
вать методы решения «в лоб» задачи о восьми ферзях, с которой вы познакоми*
лись в упражнении 7.26.


Если честно, то я и эвристикой едва решил, а тут, пока что, даже мыслей нет, как... С чего начать, так как условие задачи явно просит Решите задачу о восьми ферзях, используя технику случайного «лобового»
подхода, развитую в упражнении 7.25.
т.е. упражнение про коней, там в одно из заданий требуют чтобы решение куда пойдёт конь принималось случайно, генерировалось с помощью функции rand() , а здесь как, такой вариант не пройдёт, насколько я понимаю. Что он вообще хочет, я в толк взять не могу.

Я застопорился на этих заданиях, можно даже сказать уже отчаялся, не идёт решение и всё, такое ощущение, что я ничего и не изучал(

Кто-то же изучал по Дейтелам, доходил до этого раздела, решал или пытался решить, надеюсь на помощ. Не решением, нет , хочется самому вникнуть и решить, а задание на сколько я понял простое)
Yandex
Объявления
13.05.2016, 23:27     Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга
Ответ Создать тему
Опции темы

Текущее время: 12:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru