О 8 ферзях(Без рекурсии)

@Mechanical Poet · Регистрация: 26.10.2009

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

Пытаюсь сделать задачу о 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
#include <stdlib.h>
#include <stdio.h>
 
int board [ 8 ][ 8 ];
 
void resetQ ( int i , int j )
{
    for ( int x = 0; x < 8; x++ )
    {
        --board [x][j];
        --board [i][x];
        int k;
        k = j - i + x;
        if ( k >= 0 && k<8 )
            --board [ x ][ k ];
        k = j+i-x;
        if ( k >= 0 && k < 8 )
            --board [ x ][ k ];
    }
    board [ i ][ j ] = 0;
}
 
void setQ ( int i, int j )
{
    for ( int x = 0; x < 8; x++ )
    {
        ++board [ x ][ j ];
        ++board [ i ][ x ];
        int k;
        k = j - i + x;
        if ( k >= 0 && k < 8 )
            ++board [ x ][ k ];
        k = j + i - x;
        if ( k >= 0 && k < 8 )
            ++board [ x ][ k ];
    }
    board [ i ][ j ] = -1;
}
 
bool tryQ ( int i )
{
    bool result = false;
    bool pro=false;
    while(i < 8 )
    {
        for ( int j = 0; j < 8 ; j++)
        {
            for ( int g = 0; g < 8 ; g++ )
                {
                    if ( board [i+1][g] == 0)
                        pro=true;
                }
            if ( board [ i ][ j ] == 0 )
            {
                setQ ( i, j );
                if ( pro==false )
                {
                    resetQ ( i, j );
                }
                else
                    i++;
                if ( i == 7 )
                result = true;
            }
            pro=false;
            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;
    tryQ ( 0 );
    for ( int i = 0; i < 8; i++ )
    {
        for ( int j = 0; j < 8; j++ )
        {
            if ( board [ i ][ j ] == -1 )
            printf ( "1 " );
            else 
            printf ( "0 " );
            
        }
        printf ( "\n" );
    }
printf ( "\n" );
 
    for ( int i = 0; i < 8; i++ )
    {
        for ( int j = 0; j < 8; j++ )
        {
            printf ( "%d ", board [ i ][ j ]);
            
        }
        printf ( "\n" );
    }
 
    system ( " Pause " );
}

@SimaLiveEvil · 20.11.2010, 15:29

ну вроде как

C
1
2
3
4
5
        for ( int i = 0; i < 8; i++ ) 
        {
                for ( int j = 0; j < 8; j++ )
                      board [ i ][ j ] = 0;
        }

вот так нужно инициализировать массив...

хотя нет... разницы нет...

Добавлено через 11 минут
у Вас цикл

C
1
while(i < 8)

зацикливается на i = 6

@Mechanical Poet · 20.11.2010, 17:16 **[ТС]**

Я вижу что зацикливается на i=6, но нимагу понять почему. Я никак нимагу до конца правильно реализовать эту задачу

@Shevva · 20.11.2010, 17:20

Mechanical Poet, ты случайно не из КНУ?

@Mechanical Poet · 20.11.2010, 17:26 **[ТС]**

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

Mechanical Poet, ты случайно не из КНУ?

Нет, я из ТГУ

@Mr.X · 21.11.2010, 20:52

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
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_queens_disp;
//////////////////////////////////////////////////////////////////////////////////////
bool  last_elem_is_correct(const T_queens_disp&  queens_disp)
{
    int  pos = queens_disp.size() - 1;
    for(int i = 0; i < pos; ++i)
    {
        int diff_abs = abs(queens_disp[i] - queens_disp[pos]);
        if(!diff_abs
           || diff_abs == pos - i) return  false;
    }
    return  true;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  successfully_inc_last_elem(T_queens_disp&  queens_disp)
{   
    for(;;)
    {
        ++*queens_disp.rbegin();
        if(*queens_disp.rbegin() > '8')
        {
            return  false;
        }
        if(last_elem_is_correct(queens_disp))
        {
            return  true;
        }
    }   
}
//////////////////////////////////////////////////////////////////////////////////////
bool  get_next_queens_disposition(T_queens_disp&  queens_disp)
{
    for(;;)
    {
        if(!successfully_inc_last_elem(queens_disp))
        {
            if(queens_disp.size() == 1)
            {
                return  false;
            }
            else
            {
                queens_disp.erase(queens_disp.size() - 1);
            }
        }
        else
        {
            if(queens_disp.size() == 8)
            {
                return true;
            }
            else
            {
                queens_disp += '0';
            }
        }
    }   
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_all_queens_disposition()
{
    T_queens_disp  queens_disp_cur("0");
    std::cout << "Расстановки на шахматной доске 8 ферзей, не бьющих друг друга:"
              << std::endl;
 
    int  count = 0;
    while(get_next_queens_disposition(queens_disp_cur))
    {
        std::cout << "#"
                  << ++count
                  << ":\t"
                  << queens_disp_cur
                  << std::endl;
    }    
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    print_all_queens_disposition(); 
}

@Mechanical Poet · 26.11.2010, 00:08 **[ТС]**

Mr.X, спасибо. Но мне надо чтобы он находил одно единственное решение. Я начал писать код, но застрял. Может кто нибудь сможет помочь?

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
#include <stdlib.h>
#include <stdio.h>
 
int board [ 8 ][ 8 ];
struct NODE
{
        int cell;
        NODE *next, *prev;
};
 
NODE *first = NULL;
NODE *h = NULL;
 
void resetQ ( int i , int j )
{
    j=h->cell;
    if(h == first)
        first = NULL;
    NODE *t = h;
    h = h->prev;
    if(h)
        h->next = NULL;
    delete t;
    for ( int x = 0; x < 8; x++ )
    {
        --board [x][j];
        --board [i][x];
        int k;
        k = j - i + x;
        if ( k >= 0 && k<8 )
            --board [ x ][ k ];
        k = j+i-x;
        if ( k >= 0 && k < 8 )
            --board [ x ][ k ];
    }
    board [ i ][ j ] = 0;
}
 
void setQ ( int i, int j )
{
    if(first == NULL)
    {
        h = new NODE;
        h->prev = NULL;
        h->cell=j;
        h->next = NULL;
        first = h;
    }
    else
    {
        h->next = new NODE;
        h->next->prev = h;
        h=h->next;
        h->cell=j;
        h->next = NULL;
    }
 
    for ( int x = 0; x < 8; x++ )
    {
        ++board [ x ][ j ];
        ++board [ i ][ x ];
        int k;
        k = j - i + x;
        if ( k >= 0 && k < 8 )
            ++board [ x ][ k ];
        k = j + i - x;
        if ( k >= 0 && k < 8 )
            ++board [ x ][ k ];
    }
    board [ i ][ j ] = -1;
}
 
bool tryQ ( int i )
{
    bool result = false;
    bool w = false;
    for ( int i=0; i<8; )
    {
        for ( int j = 0; j < 8 ; j++ )
        {
            if ( board [ i ][ j ] == 0 )
            {
                setQ ( i, j );
                if ( i == 7 )
                result = true;
                else
                {
                    w = false;
                    for ( int g = 0; g < 8 ; g++ )
                        if ( board [ i+1][ g ] == 0 )
                            w=true;
                    if ( w != true )
                    {
                        resetQ ( i, j );
                    }
                    else 
                    {
                        i++;
                        break;
                    }
                }
            }
            if ( result )
                return true;
        }
    }
    return result;
}
 
int main ()
{
    for ( int i = 0; i < 8; i++ )
        for ( int j = 0; j < 8; j++ )
    board [ i ][ j ] = 0;
    tryQ ( 0 );
    for ( int i = 0; i < 8; i++ )
    {
        for ( int j = 0; j < 8; j++ )
        {
            if ( board [ i ][ j ] == -1 )
            printf ( "1 " );
            else 
            printf ( "0 " );
            
        }
        printf ( "\n" );
    }
 
    printf ( "\n" );
 
    for ( int i = 0; i < 8; i++ )
    {
        for ( int j = 0; j < 8; j++ )
        {
            printf ( "%d ", board [ i ][ j ] );          
        }
        printf ( "\n" );
    }
 
 
    system ( " Pause " );
}

@Mr.X · 26.11.2010, 23:41

Сообщение от Mechanical Poet

Mr.X, спасибо. Но мне надо чтобы он находил одно единственное решение.

В моем коде это делает функция get_next_queens_disposition.

Добавлено через 4 часа 37 минут
Для доски произвольного размера:

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
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
//////////////////////////////////////////////////////////////////////////////////////
const int  BOARD_DIM_MIN               = 1;
const int  BOARD_DIM_MAX               = 20;
char       queens_disp[BOARD_DIM_MAX]  = {'0'};
int        queens_disp_size            = BOARD_DIM_MIN;
//////////////////////////////////////////////////////////////////////////////////////
int  symb_to_int(char  symb)
{
    return (symb <= '9') 
           ? symb - '0'
           : symb - 'a' + 0xa;
}
//////////////////////////////////////////////////////////////////////////////////////
char  int_to_symb(int int_val)
{
    return (int_val <= 9)
           ? '0' + int_val
           : 'a' + int_val - 0xa;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  last_elem_is_correct()
{
    int  pos_last  = queens_disp_size - 1;
    int  diff_abs  = 0;
    for(int i = 0; i < pos_last; ++i)
    {
        int diff_abs = abs(symb_to_int(queens_disp[i]) - symb_to_int(queens_disp[pos_last]));
        if(!diff_abs
           || diff_abs == pos_last - i) return  false;
    }
    return  true;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  successfully_inc_last_elem(int  board_dim)
{    
    char&  last_elem = queens_disp[queens_disp_size - 1];
    for(;;)
    {
        last_elem = int_to_symb(symb_to_int(last_elem) + 1);      
 
        if(symb_to_int(last_elem) > board_dim)        
        {
            return  false;
        }
        if(last_elem_is_correct())
        {
            return  true;
        }
    }   
}
//////////////////////////////////////////////////////////////////////////////////////
bool  get_next_queens_disposition(int  board_dim)
{    
    for(;;)
    {
        if(!successfully_inc_last_elem(board_dim))
        {
            if(queens_disp_size == 1)
            {
                return  false;
            }
            else
            {                
                --queens_disp_size;                
            }
        }
        else
        {
            if(queens_disp_size == board_dim)
            {
                return true;
            }
            else
            {
                ++queens_disp_size; 
                queens_disp[queens_disp_size - 1] = '0';
            }
        }
    }   
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_all_queens_disposition(int  board_dim)
{    
    int  count = 0; 
    while(get_next_queens_disposition(board_dim))
    {
        ++count;
        if(count == 1)
        {
            std::cout << "Расстановки на шахматной доске размерностью "
                      << board_dim 
                      << " стольких же ферзей, "
                      << std::endl
                      << "не бьющих друг друга:"
                      << std::endl;        
        }
        std::cout << "#"
                  << count
                  << ":\t"
                  << T_str(queens_disp, queens_disp + board_dim)
                  << std::endl;
    }
 
    if(!count)
    {
        std::cout << "Не существует расстановок на шахматной доске размерностью "
                  << board_dim 
                  << " стольких же ферзей, не бьющих друг друга:"
                  << std::endl;       
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));    
 
    int  board_dim = 0;
    do
    {
        std::cout << "Введите размерность шахматной доски "
                  << BOARD_DIM_MIN
                  << " <= n <= "
                  << BOARD_DIM_MAX
                  << ": ";
 
        std::cin >> board_dim;        
    }while(board_dim < BOARD_DIM_MIN 
          || BOARD_DIM_MAX < board_dim);
 
    print_all_queens_disposition(board_dim);            
}

@-=ЮрА=- · 04.05.2012, 19:26

Учебный пример: задача о восьми ферзях

@Kuzia domovenok · 04.05.2012, 21:28

Сообщение от -=ЮрА=-

Учебный пример: задача о восьми ферзях

Просили ж без рекурсии!!!

@-=ЮрА=- · 04.05.2012, 22:24

Kuzia domovenok, у тебя претензии???
Вначале темы автору нужен был рабочий код

Сообщение от Mechanical Poet

Сделал набросок, но работает как то криво.

, надо без рекурсии правим то что дано по ссылке. Чё за наезды млин?

Evg · 05.05.2012, 19:58

Не по теме:

Сообщение от -=ЮрА=-

надо без рекурсии правим то что дано по ссылке. Чё за наезды млин?

Удивительно, почему ты не выкатил исходники ядра линукса и не сказал, что после доработки напильником получится задача о 8 ферзях

@-=ЮрА=- · 05.05.2012, 20:49

Не по теме:

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

Удивительно, почему ты не выкатил исходники ядра линукса и не сказал, что после доработки напильником получится задача о 8 ферзях

- а что они есть в инете, дай ссылку сейчас моментом сделаю:D

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@Mechanical Poet 2 / 2 / 0 Регистрация: 26.10.2009 Сообщений: 9
	20.11.2010, 17:16 [ТС]
	Я вижу что зацикливается на i=6, но нимагу понять почему. Я никак нимагу до конца правильно реализовать эту задачу 0

@Shevva 17 / 17 / 0 Регистрация: 13.09.2009 Сообщений: 140
	20.11.2010, 17:20
	Mechanical Poet, ты случайно не из КНУ? 0

@-=ЮрА=- 6614 / 4256 / 401 Регистрация: 08.08.2009 Сообщений: 10,325 Записей в блоге: 24
	04.05.2012, 19:26
	Учебный пример: задача о восьми ферзях 0