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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.80
Mechanical Poet
2 / 2 / 0
Регистрация: 26.10.2009
Сообщений: 9
20.11.2010, 14:49     О 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
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
5 / 5 / 0
Регистрация: 02.05.2010
Сообщений: 40
20.11.2010, 15:29     О 8 ферзях(Без рекурсии) #2
ну вроде как
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
2 / 2 / 0
Регистрация: 26.10.2009
Сообщений: 9
20.11.2010, 17:16  [ТС]     О 8 ферзях(Без рекурсии) #3
Я вижу что зацикливается на i=6, но нимагу понять почему. Я никак нимагу до конца правильно реализовать эту задачу
Shevva
 Аватар для Shevva
17 / 17 / 0
Регистрация: 13.09.2009
Сообщений: 140
20.11.2010, 17:20     О 8 ферзях(Без рекурсии) #4
Mechanical Poet, ты случайно не из КНУ?
Mechanical Poet
2 / 2 / 0
Регистрация: 26.10.2009
Сообщений: 9
20.11.2010, 17:26  [ТС]     О 8 ферзях(Без рекурсии) #5
Цитата Сообщение от Shevva Посмотреть сообщение
Mechanical Poet, ты случайно не из КНУ?
Нет, я из ТГУ
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
21.11.2010, 20:52     О 8 ферзях(Без рекурсии) #6
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
2 / 2 / 0
Регистрация: 26.10.2009
Сообщений: 9
26.11.2010, 00:08  [ТС]     О 8 ферзях(Без рекурсии) #7
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
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
26.11.2010, 23:41     О 8 ферзях(Без рекурсии) #8
Цитата Сообщение от 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);            
}
-=ЮрА=-
Заблокирован
Автор FAQ
04.05.2012, 19:26     О 8 ферзях(Без рекурсии) #9
Учебный пример: задача о восьми ферзях
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
04.05.2012, 21:28     О 8 ферзях(Без рекурсии) #10
Просили ж без рекурсии!!!
-=ЮрА=-
Заблокирован
Автор FAQ
04.05.2012, 22:24     О 8 ферзях(Без рекурсии) #11
Kuzia domovenok, у тебя претензии???
Вначале темы автору нужен был рабочий код
Цитата Сообщение от Mechanical Poet Посмотреть сообщение
Сделал набросок, но работает как то криво.
, надо без рекурсии правим то что дано по ссылке. Чё за наезды млин?
Evg
05.05.2012, 19:58
  #12

Не по теме:

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
надо без рекурсии правим то что дано по ссылке. Чё за наезды млин?
Удивительно, почему ты не выкатил исходники ядра линукса и не сказал, что после доработки напильником получится задача о 8 ферзях

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.05.2012, 20:49     О 8 ферзях(Без рекурсии)
Еще ссылки по теме:

C++ Написать функцию без рекурсии
Рекурсия без рекурсии C++
Разложение на простые множители без рекурсии C++

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

Или воспользуйтесь поиском по форуму:
-=ЮрА=-
05.05.2012, 20:49     О 8 ферзях(Без рекурсии)
  #13

Не по теме:

Цитата Сообщение от Evg Посмотреть сообщение
Удивительно, почему ты не выкатил исходники ядра линукса и не сказал, что после доработки напильником получится задача о 8 ферзях
- а что они есть в инете, дай ссылку сейчас моментом сделаю

Yandex
Объявления
05.05.2012, 20:49     О 8 ферзях(Без рекурсии)
Ответ Создать тему
Опции темы

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