Рекурсия в решателе судоку

@Артем Кольчик · Регистрация: 28.02.2012

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

Имеется программа, которая перебором всех возможных значений для всех пустых ячеек СУДОКУ, заполняет их значениями:
вот функция с рекурсией. Функция почему то останавливается, дойдя до ячейки, в которую нельзя ничего подставить.
PS все функции правильные этой, в которой рекурсия, в общем коде, она последняя

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var i = 0;
function getAnswer(i){ // сама функция
    if (Reshen() == false){ // проверяем решена ли судоку
        var z = getNullArray(i); // получаем координату пустой ячейки 
        for (var v = 0; v < getPosible(z).length; v++){ // getPosible(z) - возвращает массив возможных вариантов для тек. ячейки
            if (getPosible(z).length >= 0){ // если длина массива возможных вариантов больше нуля (в смысле есть ли вообще варианты)
            sudoku[z] = getPosible(z)[v]; // присваиваем вариант
            getAnswer(i+1); // углубляемся к следующей нерешенной ячейке
            
            }
            
        }
        
    } 
}
getAnswer(); 
getOutput(); // Выводим результат перебора ( он не верный и не до конца)

Ниже весь код программы для некоторого СУДОКУ:

JavaScript
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
"use strict";
var sudoku;
sudoku = [  8, 0, 0, 0, 0, 0, 0, 0, 0,
            0, 0, 3, 6, 0, 0, 0, 0, 0,
            0, 7, 0, 0, 9, 0, 2, 0, 0,
            0, 5, 0, 0, 0, 7, 0, 0, 0,
            0, 0, 0, 0, 4, 5, 7, 0, 0,
            0, 0, 0, 1, 0, 0, 0, 3, 0,
            0, 0, 1, 0, 0, 0, 0, 6, 8,
            0, 0, 8, 5, 0, 0, 0, 1, 0,
            0, 9, 0, 0, 0, 0, 4, 0, 0,
];
function SpisokVozmStroki(i) {
    var a = [];
    var start = Math.floor(i / 9);
    for (var j = start * 9; j < (start * 9 + 9); j++) {
        if (sudoku[j] != 0) {
            a.push(sudoku[j]);
        }
    }
    var b = [];
    for (var k = 1; k <= 9; k++) {
        var check = true;
        for (var z = 0; z < a.length; z++) {
            if (k == a[z]) {
                check = false;
                break;
            }
        }
        if (check == true) {
            b.push(k);
        }
    }
    return b;
}
function SpisokVozmStolb(i) {
    var a = [];
    var start = i % 9;
    for (var j = start; j < 81; j = j + 9) {
        if (sudoku[j] != 0) {
            a.push(sudoku[j]);
        }
    }
    var b = [];
    for (var k = 1; k <= 9; k++) {
        var check = true;
        for (var z = 0; z < a.length; z++) {
            if (k == a[z]) {
                check = false;
                break;
            }
        }
        if (check == true) {
            b.push(k);
        }
    }
    return b;
 
}
function Kvadrant(i) {
    // определяем номер строки в которой находится число i
    var Stroka = Math.floor(i / 9); // 1
    // определяем номер строки квадранта для числа i
    var StartStr = Math.floor(Stroka / 3) * 3; // 0
    // определяем номер столба в которой находится число i
    var Stolb = i - Math.floor(i / 9) * 9; // 4 
    // определяем номер столба квадранта для числа i
    var StartStolba = Math.floor(Stolb / 3) * 3; // 3
    var a = [];
    var start = StartStr * 9 + StartStolba;
    for (var j = start; j < (start + 3); j++) {
        if (sudoku[j] != 0) {
            a.push(sudoku[j]);
        }
    }
    for (var s = start + 9; s < (start + 12); s++) {
        if (sudoku[s] != 0) {
            a.push(sudoku[s]);
        }
    }
    for (var u = start + 18; u < (start + 21); u++) {
        if (sudoku[u] != 0) {
            a.push(sudoku[u]);
        }
    }
    var b = [];
    for (var k = 1; k <= 9; k++) {
        var check = true;
        for (var z = 0; z < a.length; z++) {
            if (k == a[z]) {
                check = false;
                break;
            }
        }
        if (check == true) {
            b.push(k);
        }
    }
    return b;
}
//список возможных цифр в данной ячейке
function getPosible(i) {
    var aStr = SpisokVozmStroki(i);
    var aStolb = SpisokVozmStolb(i);
    var aKv = Kvadrant(i);
    var a = [];
    for (var x = 1; x < 10; x++) {
        if (aStr.includes(x) && aStolb.includes(x) && aKv.includes(x)) {
            a.push(x);
        }
    }
    return a;
}
 
// Проверка решена ли судоку
function Reshen() {
    if (sudoku.includes(0)) {
        return false;
    } else {
        return true;
    }
}
 
// массив координат нулей
function getNullArray () {
    let arr = [];
    for ( var i = 0; i < sudoku.length; i++) {
        if (sudoku[i] == 0) { 
            arr.push(i);
            return arr;
         }
    }
     
}
// Вывести судоку
function getOutput(){
    for (var i = 0; i < 81; i+=9){
        var arr = [];
        for (var j = i; j < i + 9; j++){
            arr.push(sudoku[j]);
        }
        console.log(arr);
    }
    
}
// массив всех возможных значений в ячейке
function getArrPosible () {
    let arr = [];
    for (let i = 0; i < sudoku.length; i++){
        if (sudoku[i] > 0) { arr.push(sudoku[i]); }
        else { arr.push(getPosible(i)); }
        
    }
    return arr;
}
 
var i = 0;
function getAnswer(i){ // сама функция
    if (Reshen() == false){ // проверяем решена ли судоку
        var z = getNullArray(i); // получаем координату пустой ячейки 
        for (var v = 0; v < getPosible(z).length; v++){ // getPosible(z) - возвращает массив возможных вариантов для тек. ячейки
            if (getPosible(z).length >= 0){ // если длина массива возможных вариантов больше нуля (в смысле есть ли вообще варианты)
            sudoku[z] = getPosible(z)[v]; // присваиваем вариант
            getAnswer(i+1); // углубляемся к следующей нерешенной ячейке
            
            }
            
        }
        
    } 
}
getAnswer();
getOutput();

@shvyrevvg · 16.10.2019, 11:18

Артем Кольчик, как минимум в 172стр. getAnswer(0);

@Артем Кольчик · 16.10.2019, 11:35 **[ТС]**

Ничего не изменилось

@shvyrevvg · 16.10.2019, 12:25

Сообщение от Артем Кольчик

Ничего не изменилось

Артем Кольчик, тогда, как минимум, переменная i вообще не нужна.

@Артем Кольчик · 16.10.2019, 12:53 **[ТС]**

Хорошо, как тогда перейти к следующей незаполненной ячейке?

@shvyrevvg · 16.10.2019, 13:24

Сообщение от Артем Кольчик

Хорошо, как тогда перейти к следующей незаполненной ячейке?

Артем Кольчик, у функции getAnswer параметр i нигде не используется. Вы, конечно, передаете i дальше в getNullArray

Сообщение от Артем Кольчик

JavaScript
1
var z = getNullArray(i); // получаем координату пустой ячейки

но у getNullArray нет параметров

Сообщение от Артем Кольчик

JavaScript
1
2
3
4
5
6
7
8
9
10
// массив координат нулей
function getNullArray () {
* * let arr = [];
* * for ( var i = 0; i < sudoku.length; i++) {
* * * * if (sudoku[i] == 0) { 
* * * * * * arr.push(i);
* * * * * * return arr;
* * * * *}
* * }
}

@Артем Кольчик · 16.10.2019, 19:36 **[ТС]**

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

JavaScript
1
sudoku[z] = 0; // если ветвь зашла в тупик, ячейку возвращаем в исходное положение

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function getAnswer(){ // главная функция функция
    if (Reshen() == false){ // проверяем решена ли судоку
        var z = getNextNull(); // получаем координату пустой ячейки 
        var values = getPosible(z); // получаем список возможных вариантов для пустой ячейки для последующей подстановки и проверки
        if (values.length > 0){ // если длина массива возможных вариантов больше нуля (в смысле есть ли вообще варианты)
            for (var v = 0; v < values.length; v++){ // прогоняем каждый возможный элемент для данной ячейки
                sudoku[z] = values[v]; // присваиваем вариант
                getAnswer(); // углубляемся к следующей нерешенной ячейке
                sudoku[z] = 0; // если ветвь зашла в тупик, ячейку возвращаем в исходное положение
            }    
        }
    } else getOutput(); // выводим решение
}
getAnswer();

Новые блоги и статьи Все статьи Все блоги /
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .

@shvyrevvg 1786 / 1036 / 445 Регистрация: 12.05.2016 Сообщений: 2,550
	16.10.2019, 11:18
	Артем Кольчик, как минимум в 172стр. getAnswer(0); 0

@Артем Кольчик 0 / 0 / 1 Регистрация: 28.02.2012 Сообщений: 33
	16.10.2019, 11:35 [ТС]
	Ничего не изменилось 0

@Артем Кольчик 0 / 0 / 1 Регистрация: 28.02.2012 Сообщений: 33
	16.10.2019, 12:53 [ТС]
	Хорошо, как тогда перейти к следующей незаполненной ячейке? 0