0 / 0 / 0
Регистрация: 22.12.2020
Сообщений: 6
1

Генерация Судоку c++

22.12.2020, 05:24. Показов 1704. Ответов 7
Метки c++ (Все метки)

Доброго времени суток.
Нашел алгоритм генерации судоку, но не могу понять как он работает.
+- понимание есть, алгоритм работает, хотя, по идее, не должен.
В функции moveback() есть выход за границы массива. Но при этом все равно работает верно.
Объясните, пожалуйста!!!
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
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <cstdlib>
using namespace std;
 
const int SIZE = 9;
int sudoku[SIZE][SIZE];
int test_array[SIZE*SIZE][SIZE] = {0};
 
bool checkrow(int, int);
bool checkcol(int, int);
bool checksqr(int, int);
bool test(int, int);
bool CheckRepeated(int i, int j);
void moveback(int& i, int& j);
void write(int i, int j);
void print();
 
int main()
{
    srand(time(0));
    
    int i, j;
    for(i=0; i<9; i++)
    {
        for(j=0; j<9; j++)
        {
            for(;;)
            {
                if(!test(i, j))
                    moveback(i, j);
                
                sudoku[i][j] = rand()%9+1;
                
                if(CheckRepeated(i, j))
                    continue;
                    
                write(i, j);
                if(checksqr(i, j) && checkrow(i, j) && checkcol(i, j) )
                    break;
            }
        }
    }
    
     print();
    
    return 0;
    
}
 
bool checkrow(int x, int y)
{
    for(int i=0; i<y; i++)
        if(sudoku[x][i] == sudoku[x][y])
            return false;
 
    return true;
}
 
bool checkcol(int x, int y)
{
    for(int i=0; i<x; i++)
        if(sudoku[i][y] == sudoku[x][y])
            return false;
    
    return true;
}
 
bool checksqr(int x, int y)
{ 
    int i_start = x/3;      i_start *= 3;
    int j_start = y/3;      j_start *= 3;
    
    for(int i=i_start; i < i_start+3; i++)
        for(int j=j_start; j < j_start+3; j++)
        {
            if(i==x && j==y)
                return true;
            
            if(sudoku[i][j] == sudoku[x][y])
                return false;
        }
    return true;
}
 
bool test(int i, int j)
{
    int current = i*9 +j+1;
    
    for(int x=1; x<9; x++)
        if( test_array[current][x] == 0)
            return true;
 
    return false;
}
 
bool CheckRepeated(int i, int j)
{
    int value = sudoku[i][j];
    int current = i*9 +j+1;
    
    if(test_array[current][value] == 1)
        return true;
    else
        return false;
}
 
void moveback(int& i, int& j)
{
    int current = i*9 +j+1;
    
    for(int x=1; x<=9; x++)
        test_array[current][x] = 0;
    
    if(j < 1)
    {
        i--;    j=8;
    }
    else
        j--;
}
 
void write(int i, int j)
{
    int current = i*9 + j+1;
    int value = sudoku[i][j];
    test_array[current][value] = 1;
}
 
void print()
{
    int i, j;
    
    for(i=0; i<9; i++)
    {
        if( i%3 == 0 )
            cout << "=========================\n";
        
        cout << "| ";
        
        for(j=0; j<9; j++)
        {
            cout << sudoku[i][j] << " ";
            
            if((j+1)%3 == 0)
                cout << "| ";
        }
        
        cout << endl;
    }
        cout << "=========================\n";
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.12.2020, 05:24
Ответы с готовыми решениями:

Генерация и решение судоку
Никто не знает ,если ли статья про решение и ,главное, генерацию судоку с различными эвристиками с...

Судоку
6. (6 и 7 лабораторная работа) – Судоку. (6 – заполнение массива).

Судоку
# include &lt;algorithm&gt; # include &lt;iostream&gt; # include &lt;string.h&gt; # include &lt;stdio.h&gt; # include...

Судоку
Добрый день! Очень нужна помощь! Нужен код СУДОКУ на С++, задали на курсовую, ничего не...

7
553 / 531 / 85
Регистрация: 29.05.2015
Сообщений: 3,454
22.12.2020, 06:11 2
Как же он работает, если есть выход за пределы массива? Должен завершаться ошибкой.
0
0 / 0 / 0
Регистрация: 22.12.2020
Сообщений: 6
22.12.2020, 12:46  [ТС] 3
Так вот в этом-то и прикол. Алгоритм работает! Хотя и есть выход за границу массива
Но вот почему он работает я понять не могу
0
553 / 531 / 85
Регистрация: 29.05.2015
Сообщений: 3,454
22.12.2020, 16:59 4
Разве выход за пределы массива не приводит к аварийной остановке программы?
Попробую проверить сей чудесный алгоритм на Qt.

А вообще, квадратов, которые удовлетворяют требованиям судоку очень намного меньше, чем квадратов со случайным распределением цифр. И по моему мнению, получить такой квадрат рэндомом практически невозможно.

Ну вот пример судоку, которая составилась (решилась) из 15-ти исходных цифр:
Миниатюры
Генерация Судоку c++  
0
553 / 531 / 85
Регистрация: 29.05.2015
Сообщений: 3,454
23.12.2020, 00:08 5
Да, вы правы, алгоритм работает. Как - не знаю, нужно разбираться. А можно и не разбираться. Есть рабочий алгоритм - и хорошо, пусть будет. Какая-то умная голова придумала.

Что-бы убрать выход за пределы массива, нужно в строчке 7 вставить "+ 1":
C
1
7  int test_array[SIZE*SIZE + 1][SIZE] = {0};
Изображения
 
0
0 / 0 / 0
Регистрация: 22.12.2020
Сообщений: 6
23.12.2020, 01:00  [ТС] 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
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
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <cstdlib>
using namespace std;
 
const int SIZE = 9;
int sudoku[SIZE][SIZE];
int test_array[SIZE*SIZE][SIZE] = {0};
 
bool checkrow(int, int);
bool checkcol(int, int);
bool checksqr(int, int);
bool test(int, int);
bool CheckRepeated(int i, int j);
void moveback(int& i, int& j);
void write(int i, int j);
void print();
 
int main()
{
    srand(time(0));
    
    int i, j;
    for(i=0; i<9; i++)
    {
        for(j=0; j<9; j++)
        {
            for(;;)
            {
                if(!test(i, j))
                    moveback(i, j);
                
                sudoku[i][j] = rand()%9+1;
                
                if(CheckRepeated(i, j))
                    continue;
                    
                write(i, j);
                if(checksqr(i, j) && checkrow(i, j) && checkcol(i, j) )
                    break;
            }
        }
    }
    
     print();
    
    return 0;
    
}
 
bool checkrow(int x, int y)
{
    for(int i=0; i<y; i++)
        if(sudoku[x][i] == sudoku[x][y])
            return false;
 
    return true;
}
 
bool checkcol(int x, int y)
{
    for(int i=0; i<x; i++)
        if(sudoku[i][y] == sudoku[x][y])
            return false;
    
    return true;
}
 
bool checksqr(int x, int y)
{ 
    int i_start = x/3;      i_start *= 3;
    int j_start = y/3;      j_start *= 3;
    
    for(int i=i_start; i < i_start+3; i++)
        for(int j=j_start; j < j_start+3; j++)
        {
            if(i==x && j==y)
                return true;
            
            if(sudoku[i][j] == sudoku[x][y])
                return false;
        }
    return true;
}
 
bool test(int i, int j)
{
    int current = i*9 +j;
    
    for(int x=0; x<9; x++)
        if( test_array[current][x] == 0)
            return true;
 
    return false;
}
 
bool CheckRepeated(int i, int j)
{
    int value = sudoku[i][j] - 1;
    int current = i*9 +j;
    
    if(test_array[current][value] == 1)
        return true;
    else
        return false;
}
 
void moveback(int& i, int& j)
{
    int current = i*9 +j;
    
    for(int x=0; x< 9; x++)
        test_array[current][x] = 0;
    
    if(j < 1)
    {
        i--;    j=8;
    }
    else
        j--;
}
 
void write(int i, int j)
{
    int current = i*9 + j+1;
    int value = sudoku[i][j];
    test_array[current][value] = 1;
}
 
void print()
{
    int i, j;
    
    for(i=0; i<9; i++)
    {
        if( i%3 == 0 )
            cout << "=========================\n";
        
        cout << "| ";
        
        for(j=0; j<9; j++)
        {
            cout << sudoku[i][j] << " ";
            
            if((j+1)%3 == 0)
                cout << "| ";
        }
        
        cout << endl;
    }
        cout << "=========================\n";
}
0
553 / 531 / 85
Регистрация: 29.05.2015
Сообщений: 3,454
23.12.2020, 14:24 7
C
1
2
    int value = sudoku[i][j] - 1;
    int current = i*9 +j;
Странно. Вы содержимое ячейки sudoku[i][j] уменьшаете на единицу. Раньше там явно было 1-9, теперь будет 0-8. Ноль - значение неправильное, в судоку нолей не бывает. И после этого всё работает?
0
0 / 0 / 0
Регистрация: 22.12.2020
Сообщений: 6
23.12.2020, 16:16  [ТС] 8
Как ни странно, но все работает.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.12.2020, 16:16
Помогаю со студенческими работами здесь

Судоку си++
Подскажите пожалуйста как правильно создать таблицу 9*9 для ввода значений?

Судоку
Помогите написать игру судоку. я программирую в С++. Мне дали задание написать игру судоку в...

проверка судоку
Помогите пожалуйста написать программу , которая проверяет правильность решения судоку. Мне нужно...

решение судоку
Судоку размера n называется квадрат со стороной n2, разделенный на n2 средних квадратов со стороной...

почти судоку)
Уже создавала эту тему, но никто не ответил.Может не увидели или не успели.. .Если кто может помочь...

Решение Судоку
Здравствуйте! Заранее извеняюсь за повтор, писал такую тему в алгоритмах, но там глухо :( ...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru