Алгоритм генерации судоку - нужна помощь

@Миха · Регистрация: 23.12.2008

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

Сразу извиняюся за возможное повторение темы!

Необходима помощь в составлении алгоритма генерации массивов судоку.

Короткая справка:

Стандартный судоку представляет собой таблицу 9*9, заполненную цифрами от 1 до 9 по следующим правилам:
1)ни в одной строке не должно быть повторяющихся цифр

2)ни в одном столбце не должно быть повторяющихся цифр

3)двумерный массив разделен на сектора размерностью 3*3 клетки(таких секторов 9)
и в этих секторах не должно быть повторяющихся цифр

Повторяю, нужен именно алгоритм генерации исходной таблицы, а не алгоритм решения!

я смог додуматься только до такого:

1)назначаю массивы кандидатов для строк, столбцов и секторов
размерность каждого массива n*n,где n - размерность таблицы судоку
то есть если таблица судоку 4*4, то массивы кандидатов выглядят так:

с1:
1 2 3 4 //первая строка
1 2 3 4//вторая строка
1 2 3 4//третья строка
1 2 3 4//четвертая строка

тоже самое и для столбцов, и для секторов.

2)далее в двойном цикле по строкам и столбцам сначала определяем номер сектора(здесь у меня вообще сделано по дилетантски, кто подскажет более оптимальный алгоритм, буду премного благодарен) затем случайно определяем число от 1 до n, затем смотрим присутствует ли оно в массиве кандидатов на эту строчку, столбец и сектор. Если присутствует, то элементу массива судоку присваеваем это число, а в массивах кандидатов его зануляем.

Выглядит это примерно так:
Генерируем к примеру 12 элемент(все описываю для массива судоку 4*4). Номер его строки 3, номер столбца 4, номер сектора 4. Выпало число 3
тогда массивы кандидатов будут выглядеть так:

строки:
1 2 3 4
1 2 3 4
1 2 0 4
1 2 3 4

столбцы:

1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 0

сектора:

1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 0

Шаг 2 повторяем до тех пор, пока не будут сгенерированы верно все элементы.

Алгоритм у меня кривой, не хватает одного или нескольких пунктов. Если кто то знает каких пунктов не хватает у меня, или может поделиться своим алгоритмом, то прошу помочь.

в качестве реализации выбрал язык BС++:

Code
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
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
 
const int n = 4 ;
 
void init_ar ( int ar[ n ][ n ] )
 
{
 
int i , j ;
 
    for(i = 1 ; i <= n ; i++ )
 
        for( j = 1 ; j <= n ; j++ )
 
        ar[ i ][ j ] = j ;
 
}
 
void init_cands( int c1[ n ][ n ] , int c2[ n ][ n ] , int c3[ n ][ n ] )
 
{
 
init_ar( c1 ) ;
 
init_ar( c2 ) ;
 
init_ar( c3 ) ;
 
}
 
void gen_sud( int c11[ n ][ n ],int c22[ n ][ n ],int c33[ n ][ n ],int a[ n ][ n ][ n ] )
 
{
 
int z , i , j , k ;
 
randomize() ;
 
init_cands( c11 , c22 , c33 ) ;
 
    for( i = 1 ; i <= 4 ; i++ )
 
    {
 
        for( j = 1 ; j <=4 ; j++ )
 
        {
 
            if( i <= 2 && j <= 2 )
 
            k = 1 ;
 
            if( i <= 2 && j >= 3 )
 
            k = 2 ;
 
            if( i >= 3 && j <= 2 )
 
            k = 3 ;
 
            if( i >= 3 && j >= 3 )
 
            k = 4 ;
 
            z = random( 4 ) + 1 ;
 
                while( 1 )
 
                {
 
                    if( c11 [ i ][ z ] == 0 || c22[ j ][ z ] == 0 || c33[ k ][ z ] == 0 )
 
                    {
 
                    z = random( 4 ) + 1 ;
 
                    }
 
                else
 
                {
 
                c11[ i ][ z ] = 0 ;
 
                c22[ j ][ z ] = 0 ;
 
                c33[ k ][ z ] = 0 ;
 
                a[ i ][ j ][ k ] = z ;
 
                cout << " " << a[ i ][ j ][ k ] ;
 
                break ;
 
                }
 
                    }
 
            }
 
        }
 
}
 
void main()
 
{
 
clrscr();
 
int s[n][n][n],str[n][n],stb[n][n],mgrid[n][n];
 
gen_sud(str,stb,mgrid,s);
 
getch();
 
}

Моя программа выдает варианты расстановок для массива 4*4 , да и то не всегда

Можно еще реализовать алгоритм рекурсивно(читал на сайтах), но я не понимаю что представляет из себя алгоритм перебора с возвратом и каким образом с помощью него можно реализовать данную задачу(читал еще про алгоритм раскраски графа)

если кто то знает ссылку на сайт, где объясняется мой вопрос, прошу поделиться.

З.Ы.:

Прошу не кидать сслыки на сайты, где выкладывают просто исходники или алгоритм типа:
"Смотрим строчки и столбцы с секторами и проверяем, уникально ли число в данной области " - это я и так знаю.

ошибка в примере массивов кандидатов. Недосмотрел:

строки:
1 2 3 4
1 2 3 4
1 2 0 4
1 2 3 4

столбцы:

1 2 3 4
1 2 3 4
1 2 3 4
1 2 0 4

сектора:

1 2 3 4
1 2 3 4
1 2 3 4
1 2 0 4

Прогоняя по шагам программу(для массива 9*9), я понял что она зацикливается примерно в таких случаях:

2 7 4 1 9 3 6 8 5
3 6 8 4 5 7 2 1 9
1 9 5 8 6 2 4 3 7
8 4 2 7 2 5 1 9 3
5 3 9 4 2 8 7 6 X

Х - число на котором программа циклится

То есть если в общей области строки и столбца (или сектора) попадается элемент который уже ставили, то программа зацикливается.

Как сделать обработчик таких ситуаций? Тут вроде нужна рекурсия (алгоритм перебора с возвратом наверное), но я не понимаю как этот алгоритм можно применить к данной ситуации.

Прочитал что представляет из себя рекурсия, ну и попытался сгенерировать массив диагональный массив судоку(там нет разделения на сектора, а есть только проверка в главной и побочной диагонали). Составил алгоритм, он описывается так:

1. первую ячейку таблицы назначаем произвольным образом
2. заполняем следующие ячейки:

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

г. если число заполненных ячеек = 81, заканчиваем работу

вот код программы составленный вроде по алгоритму, но она почему то не работает(выдает бесконечный массив а потом вылетает). Попытался прогонять по шагам - почему то нормально ставятся только первые 6 ячеек, остальное идет с повторениями. Помогите разобраться чего не хватает в программе(может я неправильно понял принцип действия рекурсии). Помогите разобраться.

Вод код:

Code
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
#include <conio.h>
#include <stdlib.h>
#include <iostream.h>
 
int const n=9;
 
void init(int a[n][n])//inicializacia tablici(prisvaivaem 0)
{
int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        a[i][j]=0;
}
 
int unic(int a[n][n],int ci,int cj,int k)//unicalnost v stroke,stolbze i diagonali
{
int i,j,f=0;
    for(i=1;i<=n;i++)
        if(a[i][cj]==k) f++;
            for(j=1;j<=n;j++)
                if(a[ci][j]==k) f++;
    if(ci==cj)
    {
        for(i=1;i<=n;i++)//glavnaia diagonal
            if(a[i][i]==k) f++;
    }
        else
            if(cj==n-ci+1)
            {
                for(i=1;i<=n;i++)//pobochnaia diagonal
                    if(a[i][n-i+1]==k) f++;
            }
return f;
}
 
void rec(int a[n][n],int i,int j)//recursia dlia zapolnenia tablici
{
int it,jt,fl,num;
    for(it=i;it<=n;it++)
    {
        for(jt=j;jt<=n;jt++)
        {
        num=random(9)+1;
        fl=unic(a,it,jt,num);
                if(fl==0)//esli sovpadenii net
                {
                a[it][jt]=num;
                cout<<" "<<a[it][jt];
                if(jt==9) cout<<"\n";
                }
                    else//ecli est sovpadenia, to vozvrashemsia k 
                                                        //predidushei iacheike
                    {
                        if(jt==1&&it>1)
                            rec(a,it-1,jt+8);
                                else
                                rec(a,it,jt-1);
                    }
 
        }
    }
}
 
void main()
{
clrscr();
randomize();
int s[n][n];
int i,j;
init(s);
s[1][1]=random(9)+1;
rec(s,1,2);
getch();
}

Получилось написать програмку генерации правильного судоку с разделением на сектора, теперь встал вопрос о правильном удалении элементов в таблице таким образом, чтобы имелось одно решение. Я вроде составил алгоритм, он вот:

1. выбираем случайным образом координаты ячейки
2. если встретили ячейку с цифрой ноль(т.е. уже удаленную) то возвращаемся на шаг 1, иначе шаг 3
3. сохраняем значение ячеки в какой нибудь буфферной переменной и ставим цифру 0 в данную ячейку
4. восстанавливаем значение предыдущего удаленного элемента таблицы
5. если текущему (т. е. не предыдущему удаленному, а удаленному на данном шаге элементу) можно сопоставить более одного значения из набора 1 2 3 4 5 6 7 8 9 таким образом, чтобы они не противоречили правилам судоку,то возвращаемся на шаг 1, иначе данную ячейку оставляем с цифрой 0.

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

Помогите, чем сможете.

@maximus09 · 29.12.2008, 20:59

Предлагаю алгоритм генерации судоку, основанный на использовании уже ранее сгенерированных судоку.

Разберем на простом примере
В качестве исходной можно взять следующую судоку:
1234
2341
3412
4123
(каждая новая строка получается из предыдущей сдвигом вправо по кольцу).

Для генерации следующей судоку достаточно переставить местами две случайно выбранные

строки (например, первую и третью). Получим новую судоку
3412
2341
1234
4123

Далее генерируем новую судоку путем перестановки в предыдущей любых двух случайно выбранных столбцов (например столбцов с номерами 3 и 4):
3421
2314
1243
4132
и т.д.

Теоретически все это можно продолжать до бесконечности, однако, думаю, после 10 перестановок строк и столбцов новый вариант судоку будет значительно отличаться от исходного.

Перейдем теперь к генерации реальной судоку.
Вернемся теперь к судоку 9x9. Эти судоку, как известно, разделяются на 9 "больших" полей размера 3x3 (т.е. одно "большое" поле представляет собой квадрат из 9=3x3 "маленьких" полей).
Для генерации таких судоку нужно сочетать перестановку строк и столбцов "больших" полей с перестановкой строк и столбцов "маленьких" полей внутри "большого".

Например:
123 456 789
456 789 123
789 123 456

231 564 897
564 897 231
897 231 564

312 645 978
645 978 312
978 312 645

(в данной исходной судоку 9 "больших" полей отделены друг от друга пробелами и пустыми строками).

Для генерации новой судоку достаточно переставить местами любые две "большие" строки (или два "больших" столбца - на выбор). Например, переставим первую и третью "большую" строку.
312 645 978
645 978 312
978 312 645

231 564 897
564 897 231
897 231 564

123 456 789
456 789 123
789 123 456

Это уже новое судоку.

Теперь в последней сгенерированной судоку переставим первый и третий "большие" столбцы:
978 645 312
312 978 645
645 312 978

897 564 231
231 897 564
564 231 897

789 456 123
123 789 456
456 123 789

Следующую судоку сгенерим таким образом: возьмем случайно выбранную "большую строку". Например, вторую:
897 564 231
231 897 564
564 231 897

Переставим в ней две случайно-выбранные маленькие строки (например вторую и третью). Получим
897 564 231
564 231 897
231 897 564

Добавим получившуюся "большую" строку вместо второй "большой" строки последней сгенерированной судоку, получим
978 645 312
312 978 645
645 312 978

897 564 231
564 231 897
231 897 564

789 456 123
123 789 456
456 123 789

Это новое судоку.

Почти аналогично поступаем со случаным образом выбранным "большим" столбцом в последней сгенерированной судоку. Пусть это будет первый столбец.
978
312
645

897
564
231

789
123
456

Переставим в нем два случайно выбранных "маленьких" столбца (например, первый и второй):
798
132
465

987
654
321

879
213
546

Добавим новый большой столбец в последнюю сгенерированную судоку:
798 645 312
132 978 645
465 312 978

987 564 231
654 231 897
321 897 564

879 456 123
213 789 456
546 123 789

Комбинируй все изложенные здесь отдельные приемы по несколько раз каждый, в произвольном сочетании друг с другом, чтобы получить судоку, значительно отличающуюся от исходной.

Конечно, при желании могу все вышесказанное оформить в виде блок-схемы. Но, думаю, алгоритм и так ясен и любой (даже начинающий программист) способен написать под него программу.

@PointsEqual · 14.10.2009, 20:44

посмотри тут http://www.deco.tu2.ru/arch/archive.html

Новые блоги и статьи Все статьи Все блоги /
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 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@maximus09 32 / 32 / 4 Регистрация: 29.12.2008 Сообщений: 75
	29.12.2008, 20:59
	Сообщение было отмечено как решение Решение Предлагаю алгоритм генерации судоку, основанный на использовании уже ранее сгенерированных судоку. Разберем на простом примере В качестве исходной можно взять следующую судоку: 1234 2341 3412 4123 (каждая новая строка получается из предыдущей сдвигом вправо по кольцу). Для генерации следующей судоку достаточно переставить местами две случайно выбранные строки (например, первую и третью). Получим новую судоку 3412 2341 1234 4123 Далее генерируем новую судоку путем перестановки в предыдущей любых двух случайно выбранных столбцов (например столбцов с номерами 3 и 4): 3421 2314 1243 4132 и т.д. Теоретически все это можно продолжать до бесконечности, однако, думаю, после 10 перестановок строк и столбцов новый вариант судоку будет значительно отличаться от исходного. Перейдем теперь к генерации реальной судоку. Вернемся теперь к судоку 9x9. Эти судоку, как известно, разделяются на 9 "больших" полей размера 3x3 (т.е. одно "большое" поле представляет собой квадрат из 9=3x3 "маленьких" полей). Для генерации таких судоку нужно сочетать перестановку строк и столбцов "больших" полей с перестановкой строк и столбцов "маленьких" полей внутри "большого". Например: 123 456 789 456 789 123 789 123 456 231 564 897 564 897 231 897 231 564 312 645 978 645 978 312 978 312 645 (в данной исходной судоку 9 "больших" полей отделены друг от друга пробелами и пустыми строками). Для генерации новой судоку достаточно переставить местами любые две "большие" строки (или два "больших" столбца - на выбор). Например, переставим первую и третью "большую" строку. 312 645 978 645 978 312 978 312 645 231 564 897 564 897 231 897 231 564 123 456 789 456 789 123 789 123 456 Это уже новое судоку. Теперь в последней сгенерированной судоку переставим первый и третий "большие" столбцы: 978 645 312 312 978 645 645 312 978 897 564 231 231 897 564 564 231 897 789 456 123 123 789 456 456 123 789 Следующую судоку сгенерим таким образом: возьмем случайно выбранную "большую строку". Например, вторую: 897 564 231 231 897 564 564 231 897 Переставим в ней две случайно-выбранные маленькие строки (например вторую и третью). Получим 897 564 231 564 231 897 231 897 564 Добавим получившуюся "большую" строку вместо второй "большой" строки последней сгенерированной судоку, получим 978 645 312 312 978 645 645 312 978 897 564 231 564 231 897 231 897 564 789 456 123 123 789 456 456 123 789 Это новое судоку. Почти аналогично поступаем со случаным образом выбранным "большим" столбцом в последней сгенерированной судоку. Пусть это будет первый столбец. 978 312 645 897 564 231 789 123 456 Переставим в нем два случайно выбранных "маленьких" столбца (например, первый и второй): 798 132 465 987 654 321 879 213 546 Добавим новый большой столбец в последнюю сгенерированную судоку: 798 645 312 132 978 645 465 312 978 987 564 231 654 231 897 321 897 564 879 456 123 213 789 456 546 123 789 Комбинируй все изложенные здесь отдельные приемы по несколько раз каждый, в произвольном сочетании друг с другом, чтобы получить судоку, значительно отличающуюся от исходной. Конечно, при желании могу все вышесказанное оформить в виде блок-схемы. Но, думаю, алгоритм и так ясен и любой (даже начинающий программист) способен написать под него программу. 5

@PointsEqual ниначмуроФ 851 / 535 / 110 Регистрация: 12.10.2009 Сообщений: 1,913
	14.10.2009, 20:44
	посмотри тут http://www.deco.tu2.ru/arch/archive.html 0

Алгоритм генерации судоку - нужна помощь

Решение