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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
Icewinder
1 / 1 / 0
Регистрация: 30.09.2012
Сообщений: 31
#1

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

09.12.2012, 15:25. Просмотров 2410. Ответов 14
Метки нет (Все метки)

Нужно написать программу которая расставляет на шахматной доске 8 ферзей, которые не бьют друг друга.
обязательно использование рекурсии, ну и struct .
Извините если такая тема была, интернет 64кбитный.
Спасибо =)

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

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

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

Расставить на доске N ферзей так, чтобы они не били друг друга - C++
смысл в том чтобы расставить на шахматной доске размером N*N, N ферзей так, чтобы они не били друг друна. пыиался сделать что то методом...

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

Определить бъют ли две фигуры на шахматной доске друг друга - C++
Привет. Помогите пожалуйста. Даны координаты двух фигур на шахматной доске. Определить бьют ли они друг друга. Фигуры могут быть или двое...

Сколько коней можно без угроз друг другу расставить на шахматной доске размером M на N - C++
Сколько коней можно без угроз друг другу расставить на шахматной доске размером M на N. ;)

Рекурсия: найти число расстановок N ладей, которые симметричны относительно диагоналей и не бьют друг друга - C++
Вычислить рекурсивно число расстановок N ладей на доске N*N таких, что ладьи симметричны относительно обеих диагоналей и не бьют друг...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
09.12.2012, 15:27 #2
рекурсией
я прочитал впервые о решении в книжке Окулова.
Icewinder
1 / 1 / 0
Регистрация: 30.09.2012
Сообщений: 31
09.12.2012, 15:32  [ТС] #3
А что за книга?Программирование в алгоритмах? или основы программирования?

Добавлено через 2 минуты
Да и тем более там паскаль, ну и обычный с, а плюсов нет
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
09.12.2012, 16:47 #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  [ТС] #5
Большое спасибо, добрый человек. Вроде разобрался
System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 16:59 #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
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
08.04.2015, 17:25 #7
System16v, код дикая ересь. Мало того что сама попытка перебора неоптимальна. Так ещё в ней какой-то рандом используется. Поясни, ты надеешься, что рандомно ззаполняя доску ферзями, ты рано или поздно получишь решение? Программисты никогда на такое не надеются.
System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 17:25 #8
Вот например добавил,чтоб если после завершения цикла остался пустой символ,заменить его на ферзя(знак доллара взял).У меня такое ощущение что while зацикливается....вот только почему??Сколько раз ни запускал,не видел,чтоб количество обнулений массива при поиске решения было бы больше 0 или больше 1,оно почему то всегда равно единице...как буд-то всегда хоть раз, но массив в цикле обнуляется.А в следующий раз когда нужно обнулить уже не обнуляет из-за чего похоже виснет на рандомных координатах и continue
Миниатюры
Расставить 8 ферзей на шахматной доске 8 на 8, которые не бьют друг друга  
System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 17:27 #9
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
ты рано или поздно получишь решение?
Ну типа того,что рано или поздно он должен найти решение.Рандом используется только для выбора произвольных координат,если место в массиве после выбора координат занято,то выбирается заново рандомная координата.Просто как ни пытался понять,как подобрать координаты рандомно,но по очереди перебирая все варианты - получалась какая-та ерунда. Так а циклится он от чего?
marat_miaki
107 / 96 / 36
Регистрация: 08.04.2013
Сообщений: 346
08.04.2015, 17:27 #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
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 17:35 #11
Да готовый код я видел,мне просто интересно понять где ошибка в моем коде и почему цикл зацикливается периодически .Пытаюсь разобраться просто в последовательности ходов какие делаются по циклам,и не нахожу тот случай там, при котором бы зацикливался цикл.
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
08.04.2015, 18:38 #12
marat_miaki, ничего хорошего в этом варианте не вижу. Г**но какое-то.
marat_miaki
107 / 96 / 36
Регистрация: 08.04.2013
Сообщений: 346
08.04.2015, 18:40 #13
Ну да только это Г**но все 92 варианта выдает
System16v
3 / 3 / 0
Регистрация: 19.02.2014
Сообщений: 115
08.04.2015, 18:48 #14
Ну а мой код выдает 1 правильный результат,вот если бы еще с 1го раза ....было бы вообще отлично
Liss29
23 / 12 / 2
Регистрация: 18.11.2012
Сообщений: 485
Завершенные тесты: 1
13.05.2016, 23:27 #15
( Восемь ферзей: методы решения «в лоб») В этом упражнении вы будете разви*
вать методы решения «в лоб» задачи о восьми ферзях, с которой вы познакоми*
лись в упражнении 7.26.


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

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

Кто-то же изучал по Дейтелам, доходил до этого раздела, решал или пытался решить, надеюсь на помощ. Не решением, нет , хочется самому вникнуть и решить, а задание на сколько я понял простое)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2016, 23:27
Привет! Вот еще темы с ответами:

На шахматной доске стоят три ферзя. найти ту пару из них которые угрожают друг другу! - C++
помогите пожалуйста, или подскажите как начать)) на шахматной доске стоят три ферзя. найти ту пару из них которые угрожают друг другу!

Варианты размещения восьми ферзей на шахматной доске - C++
Само задание: Найти все варианты размещения восьми ферзей на шахматной доске таким образом, чтобы никакие две фигуры не размещались на...

Расставить 8 Ферзей на шахмотной доске... в борланд С - C++
Расставить 8 ферзей на шахматной доске, чтобы они не били друг друга.... Программу надо выполнить Borland C компилятор DOSA. ...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.05.2016, 23:27
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru