Форум программистов, компьютерный форум, киберфорум
Exerion
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  

Алгоритм генерирования поля для игры "Судоку"

Запись от Exerion размещена 27.04.2013 в 15:34
Показов 312 Комментарии 0

Цитата Сообщение от Exerion Посмотреть сообщение
Всё не так просто, как два вложенных друг в друга цикла.
Делать было нечего, задачка показалась интересной, поэтому за два часа наговнокодил первое, что пришло в голову:
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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
class Program
    {
        private static int[,] playField = new int[9, 9];
        private static List<int> wrongNumbers = new List<int>();
 
        static void Main(string[] args)
        {
            Console.WriteLine("Press ENTER to generate field");
            Console.ReadLine();
 
            InitField();
            bool result = false;
            result = GenerateField();
            while (!result)
            {
                Console.WriteLine("\n\nGeneration failed. Press ENTER to generate again.\n");
                Console.ReadLine();
                result = GenerateField();
            }
 
            Console.WriteLine("Generated field:\n\n");
            PrintField();
            Console.ReadLine();
        }
 
        private static void InitField()
        {
            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                    playField[i, j] = 0;
        }
 
        private static bool CheckLine(int line, int number)
        {
            for (int i = 0; i < 9; i++)
            {
                if (playField[line, i] == number)
                {
                    Console.WriteLine("[line-" + line + "] number " + number + "banned");
                    if(!wrongNumbers.Contains(number))
                        wrongNumbers.Add(number);
                    return true;
                }
            }
            Console.WriteLine("[line-" + line + "] number " + number + "passed!");
            return false;
        }
 
        private static bool CheckColumn(int col, int number)
        {
            for (int j = 0; j < 9; j++)
            {
                if (playField[j, col] == number)
                {
                    Console.WriteLine("[col-" + col + "] number " + number + "banned");
                    if (!wrongNumbers.Contains(number))
                        wrongNumbers.Add(number);
                    return true;
                }
            }
            Console.WriteLine("[col-" + col + "] number " + number + "passed!");
            return false;
        }
 
        private static bool CheckBlock(int line, int col, int number)
        {
            int blockLine = 0;
            int blockCol = 0;
 
            double blockNum = 0;
            blockNum = line + 1;
            blockNum = blockNum / 3;
            blockNum = Math.Ceiling(blockNum);
            blockLine = Convert.ToInt32(blockNum);
 
            blockNum = col + 1;
            blockNum = blockNum / 3;
            blockNum = Math.Ceiling(blockNum);
            blockCol = Convert.ToInt32(blockNum);
 
            if (blockLine == 0) blockLine = 1;
            if (blockCol == 0) blockCol = 1;
 
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (playField[i + (blockLine - 1) * 3, j + (blockCol - 1) * 3] == number)
                    {
                        Console.WriteLine("[block " + blockLine + "-" + blockCol + " (" + line + "+" + col + ")] banned number: " + number);
                        if (!wrongNumbers.Contains(number))
                            wrongNumbers.Add(number);
                        return true;
                    }
                }
            }
            return false;
        }
 
        private static bool GenerateField()
        {
            Random rnd = new Random();
            int number = 0;
            bool result = true;
 
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    number = rnd.Next(1, 10);
                    result = CheckLine(i, number);
                    while (result)
                    {
                        number = rnd.Next(1, 10);
                        if (wrongNumbers.Count > 8)
                        {
                            InitField();
                            wrongNumbers.Clear();
                            return false;
                        }
                        while (wrongNumbers.Contains(number))
                            number = rnd.Next(1, 10);
                        result = CheckLine(i, number);
                    }
 
                    result = CheckColumn(j, number);
                    if (result)
                    {
                        j--;
                        continue;
                    }
 
                    result = CheckBlock(i, j, number);
                    if (result)
                    {
                        j--;
                        continue;
                    }
 
                    playField[i, j] = number;
                    Console.WriteLine(number + "  [!] number " + number + " accepted!\nPlayField[" + i + "," + j + "] = " + number);
                    wrongNumbers.Clear();
                }
            }
            return true;
        }
 
        private static void PrintField()
        {
            // ─ │ ┌ ┐ └ ┘ ├ ┤ ┬ ┴ ┼
            // ═ ║ ╔ ╗ ╚ ╝ ╠ ╣ ╦ ╩ ╬
            // ╒ ╓ ╕ ╖ ╘ ╙ ╛ ╜
            // ╞ ╟ ╡ ╢ ╤ ╥ ╧ ╨ ╪ ╫ 
 
            Console.WriteLine("╔══╤══╤══╦══╤══╤══╦══╤══╤══╗");
            for (int i = 0; i < 3; i++)
            {
                PrintLine(i * 3);
                Console.WriteLine("╟──┼──┼──╫──┼──┼──╫──┼──┼──╢");
                PrintLine(i * 3 + 1);
                Console.WriteLine("╟──┼──┼──╫──┼──┼──╫──┼──┼──╢");
                PrintLine(i * 3 + 2);
                if(i != 2)
                    Console.WriteLine("╠══╪══╪══╬══╪══╪══╬══╪══╪══╣");
            }
            Console.WriteLine("╚══╧══╧══╩══╧══╧══╩══╧══╧══╝");
        }
        private static void PrintLine(int line)
        {
            Console.WriteLine(
                "║" + playField[line, 0] + " │" + playField[line, 1] + " │" + playField[line, 2] + " ║" +
                playField[line, 3] + " │" + playField[line, 4] + " │" + playField[line, 5] + " ║" +
                playField[line, 6] + " │" + playField[line, 7] + " │" + playField[line, 8] + " ║");
        }
    }
Ранее мне казалось, что составить судоку - просто, бери да заполняй таблицу, следуя правилам. Как оказалось на примере программы - очень часто попадаешь в тупиковую ситуацию, когда таблица заполнена отсилы на половину, ни разу правила не нарушались, а новое число уже вписать нельзя.
Отсюда выходит, что генерация рабочего варианта судоку в зависимости от воли Великого Рандома может занять от нескольких секунд до десятка минут с учётом всех отброшенных "тупиковых" вариантов.

P.S. Строчку после сообщения о провале генерации можно закомментить, чтобы каждый раз не тыкать на энтер.
Схоронил, как говорится.
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 0
Комментарии
 
Новые блоги и статьи
Был там один разговор по поводу свободы в материальном мире.
kumehtar 19.08.2026
Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .
Когда логика программы не спасает от человеческих ошибок
Maks 18.08.2026
В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .
Лето уходит
kumehtar 17.08.2026
Мысли в слух
kumehtar 17.08.2026
Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега
Maks 17.08.2026
Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .
Саморегулирующийся социальный контракт для сервера cross-section.
Hrethgir 14.08.2026
С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .
Часы электронные
Uhbif79 12.08.2026
Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .
Часы с будильником на основе класса QLCDNumber
Uhbif79 12.08.2026
Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru