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

Получить все расстановки 8 ладей - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
VovaMazur
-12 / 33 / 8
Регистрация: 10.03.2011
Сообщений: 133
19.12.2011, 16:05     Получить все расстановки 8 ладей #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
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream>
 
const int BS = 8;
enum CellState { Free = 0, Queen, UnderAttack };
 
struct ChessBoard
{
 
    ChessBoard()
    {
        for(int r = 0; r < BS; ++r)
            for(int c = 0; c < BS; ++c)
                cells[r][c] = Free;
    }
 
    void placeQueen(int r0, int c0)
    {
        int r, c;
        cells[r0][c0] = Queen;
        for(c = c0 - 1; c >= 0; --c) cells[r0][c] = UnderAttack;
        for(c = c0 + 1; c < BS; ++c) cells[r0][c] = UnderAttack;
        for(r = r0 - 1; r >= 0; --r) cells[r][c0] = UnderAttack;
        for(r = r0 + 1; r < BS; ++r) cells[r][c0] = UnderAttack;
        for(r = r0 - 1, c = c0 - 1; r >= 0 && c >= 0; --r, --c) cells[r][c] = UnderAttack;
        for(r = r0 + 1, c = c0 + 1; r < BS && c < BS; ++r, ++c) cells[r][c] = UnderAttack;
        for(r = r0 - 1, c = c0 + 1; r >= 0 && c < BS; --r, ++c) cells[r][c] = UnderAttack;
        for(r = r0 + 1, c = c0 - 1; r < BS && c >= 0; ++r, --c) cells[r][c] = UnderAttack;
    }
 
    CellState cells[BS][BS];
};
 
void placeQueens(int count, ChessBoard &board)
{
    if(count)
    {
        for(int r = 0; r < BS; ++r)
            for(int c = 0; c < BS; ++c)
                if(!board.cells[r][c])
                {
                   ChessBoard b = board;
                   b.placeQueen(r, c);
                   placeQueens(count - 1, b);
                }
    }
    else
    {
        
        for(int r = 0; r < BS; ++r)
        {
            for(int c = 0; c < BS; ++c) std::cout << ((board.cells[r][c] == Queen) ? "Q " : "* ");
            std::cout << std::endl;
        }
       
        exit(0); 
    }
}
 
int main(int, char *[])
{
    ChessBoard board;
    placeQueens(BS, board);
    getch();
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
19.12.2011, 16:09     Получить все расстановки 8 ладей #2
В задании все ладьи - разноцветные что ли?) я это к чему - черная ладья не может угрожать другой черной ладье.
И что значит "получить все расстановки"? Их надо все на экран вывести что ли? Или просто кол-во выдать?

Если все ладьи действительно "разноцветные", то тогда задача сводится к следующему - нужно найти все восьмизначные восьмеричные числа, у которых все цифры - разные.
VovaMazur
-12 / 33 / 8
Регистрация: 10.03.2011
Сообщений: 133
21.12.2011, 21:29  [ТС]     Получить все расстановки 8 ладей #3
Ладьи все одинаковые. И их надо вывести на екран ... !

Добавлено через 1 минуту
В смысле их расстановки вывести на екран
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.12.2011, 08:32     Получить все расстановки 8 ладей #4
Вариант с рекурсией.
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
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <iostream>
 
const int BS = 8;
bool board[BS][BS], a[8];  
 
void pr()
{
    std::cout<<std::endl;
    for(int i=0; i<BS; i++)
    {
        for(int j=0; j<BS; j++)
            if(board[i][j])
                std::cout<<"*";
            else
                std::cout<<".";
            std::cout<<std::endl;
    }
 
}
 
void rec(int ii)
{
    if(ii==8)
    {
        pr();
        return;
    }
    for(int i=0; i<BS; i++)
        if(!a[i])
        {
            a[i]=true;
            board[ii][i]=true;
            rec(ii+1);
            board[ii][i]=false;
            a[i]=false;
        }
}
 
int main(int, char *[])
{   
    for(int i=0; i<BS; i++)
    {
        a[i]=true;
        board[0][i]=true;
        rec(1);
        board[0][i]=false;
        a[i]=false;
    }
    
        getch();
    return 0;
}
Лучше если выводить результаты в файл. Время работы примерно 7 сек.
VovaMazur
-12 / 33 / 8
Регистрация: 10.03.2011
Сообщений: 133
24.12.2011, 01:29  [ТС]     Получить все расстановки 8 ладей #5
А как нибудь на Чистом Си можно? Я сам не справлюсь =(
То есть мне нужно через printf и scanf ... !

Добавлено через 4 часа 26 минут
Цитата Сообщение от valeriikozlov Посмотреть сообщение
std::cout<<"*"; else std::cout<<"."; std::cout<<std::endl;
Я реально не знаю как заменить эти строки ... ((
greeezz
272 / 165 / 4
Регистрация: 10.07.2011
Сообщений: 441
24.12.2011, 01:39     Получить все расстановки 8 ладей #6
Цитата Сообщение от VovaMazur Посмотреть сообщение
std::cout<<"*"; else std::cout<<"."; std::cout<<std::endl;
C
1
2
3
std::cout<<"*"; -> printf("*");
std::cout<<"."; -> printf(".");
std::endl; -> printf("\n");
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.12.2011, 01:58     Получить все расстановки 8 ладей
Еще ссылки по теме:

C++ Проверить правильность расстановки скобок
Проверка правильности расстановки скобок в строке (рекурсия) C++
Проверить правильность расстановки в тексте круглых скобок C++

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

Или воспользуйтесь поиском по форуму:
VovaMazur
-12 / 33 / 8
Регистрация: 10.03.2011
Сообщений: 133
24.12.2011, 01:58  [ТС]     Получить все расстановки 8 ладей #7
спасибо большое )))
Yandex
Объявления
24.12.2011, 01:58     Получить все расстановки 8 ладей
Ответ Создать тему
Опции темы

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