Почему программа зацикливается при переборе?

Question

[Vernal96]

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

int i, j, k;
            string text;
            int[] arr = new int[81];
            int[,,] arr1 = new int[81, 3, 9];
            //прием данных        
            i = 0;
            foreach (Control control in Controls)
            {
                TextBox tb = control as TextBox;
                if (tb != null)
                {
                    if (tb.Text != String.Empty)
                    {
                        arr[i] = Convert.ToInt32(tb.Text);
                        i++;
                    }
                    else
                    {
                        arr[i] = 0;
                        i++;
                    }
                }
            }
            //перенос данных в рабочий массив
            /*
            arr1[i,0] - здесь найденное решение 
            arr1[i,0,8] - здесь значение задается если цифра задана в условии
            arr1[i,1] - здесь кандидаты
            arr1[i,2] - здесь уже использованные кандидаты
            */
            for (i = 0; i < 81; i++)
            {
                arr1[i, 0, 0] = arr[i];
                if (arr[i] > 0)
                {
                    arr1[i, 0, 8] = arr[i];
                }
                if (arr[i] == 0)
                {
                    for (j = 0; j < 9; j++)
                    {
                        arr1[i, 1, j] = j + 1;
                    }
                }
            }


            //решение
            for (i = 0; i < 81; i++)
            {
                if (arr1[i, 0, 8] == 0) 
                {
                    for (j = 0; j < 9; j++)
                    {
                        arr1[i, 1, j] = j + 1;
                    }
                    constriction(i, arr1); //сокращение кандидатов
                    k = 0;
                    for (j = 0; j < 9; j++)
                    {
                        if (arr1[i, 1, j] > 0)
                        {
                            if (arr1[i, 1, j] == arr1[i, 2, j]) arr1[i, 1, j] = 0;
                            else k++;
                        }
                    }
                    if (k > 0)
                    {
                        for (j = 0; j < 9; j++)
                        {
                            if (arr1[i, 1, j] > 0 && arr1[i,2,j] == 0)
                            {
                                arr1[i, 0, 0] = arr1[i, 1, j];
                                arr1[i, 2, j] = arr1[i, 1, j];
                               break;
                            }
                        }
                    }
                    else
                    {
                        arr1[i, 0, 0] = 0;
                        for (j = 0; j < 9; j++)
                        {
                            arr1[i, 2, j] = 0;
                        }
                        i--;
                        while(arr1[i,0,8] > 0 && i > 0)
                        {
                            i--;
                        }
                        if (i != 0)
                        {
                            i--;
                        }
                    }
                }
            }

Код функции сокращения кандидатов:

int x, j, y;
            //сокращение в строке
            x = i;
            while (x % 9 != 0)
            {
                x--;
            }
            for (j = x; j < x + 9; j++)
            {
                if (j != i)
                {
                    if (arr1[j, 0, 0] > 0) arr1[i, 1, arr1[j, 0, 0] - 1] = 0;
                }
            }
            //сокращение в столбце
            y = i;
            while (y > 8)
            {
                y--;
            }
            for (j = y; j < y + 73; j += 9)
            {
                if (j != i)
                {
                    if (arr1[j, 0, 0] > 0) arr1[i, 1, arr1[j, 0, 0] - 1] = 0;
                }
            }
            //сокращение в сегменте
            x = i - x;
            y = i - y;
            if (x < 3) x = 1;
            if (x > 2 && x < 6) x = 2;
            if (x > 5) x = 3;
            if (y <= 18) y = 1;
            if (y > 18 && y < 54) y = 2;
            if (y >= 54) y = 3;
            x *= y;
            switch (x)
            {
                case 1:
                    {
                        x = 0;
                        break;
                    }
                case 2:
                    {
                        x = 3;
                        break;
                    }
                case 3:
                    {
                        x = 6;
                        break;
                    }
                case 4:
                    {
                        x = 27;
                        break;
                    }
                case 5:
                    {
                        x = 30;
                        break;
                    }
                case 6:
                    {
                        x = 33;
                        break;
                    }
                case 7:
                    {
                        x = 54;
                        break;
                    }
                case 8:
                    {
                        x = 57;
                        break;
                    }
                case 9:
                    {
                        x = 60;
                        break;
                    }
            }
            for (j = x; j < x + 19; j+= 9)
            {
                for (y = j; y < j + 3; y++)
                {
                    if (y != i)
                    {
                        if (arr1[y, 0, 0] > 0) arr1[i, 1, arr1[y, 0, 0] - 1] = 0;
                    }
                }
            }

Comments

[Толстый Лорри]

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

Вы пробовали проходить алгоритм дебаггером? Где код циклится?

[Vernal96]

Free_ze: Сам код написан в первой части. Часть кода где сокращаются кандидаты работает корректно. Код начинает зацикливаться почему то не сразу а на 22 или 23 цикле. А дебаггером проверять невероятно долго, ну или я просто не умею им пользоваться

[Толстый Лорри]

Vernal96: > А дебаггером проверять невероятно долго, ну или я просто не умею им пользоваться

Вряд ли дольше, чем вникать в код)
В VS есть условные брейкпоинты, так что можно настроить их на определенную итерацию.

[Vernal96]

Free_ze: Попробую воспользоваться этим

Answer 1

[Зелимхан Бельтоев]

Не думаю, что кто-нибудь будет вдаваться в подробности такого не читаемого кода, поэтому предлагаю вам решить проблему самостоятельно, открыв для себя такое чудесное слово, как "Отладчик".

Все очень просто: поставьте после каждого цикла while и for (на всякий случай) точки остановки. Запустите программу и каждую точку, на которой остановится отладчик, просто пропустите клавишей F5. В итоге, как только программа "зациклится", вы будете знать, до какой точки вы не дошли, следовательно, виновен будет цикл, стоящий до этой точки остановки.

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

UPD:
Присмотрелся к коду:

for (i = 0; i < 81; i++) <-----
            {
...
                        i--; <-----
                        while(arr1[i,0,8] > 0 && i > 0)
                        {
                            i--; <-----
                        }
                        if (i != 0)
                        {
                            i--; <-----
                        }

Уловили? =)

Comments

[Vernal96]

Спасибо

[Vernal96]

Ну так, первый -- это откат к пред идущему, затем в случае если этот пред идущий и перед ним пред идущие заданы в условии я еще откатываю, ну а последний -- это просто откат на еще одну позицию, чтобы i осталось не на той позиции на которой была, а на пред идущей. Не уловил =((

[Vernal96]

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

[Зелимхан Бельтоев]

Vernal96: я к тому, что, скорее всего, параметр i у вас так и не становится большим или равным 81, отсюда и идёт "зацикливание".
Если запакуете решение, предварительно вбив вручную входные данные (чтобы можно было запустить и сразу на зацикливание выйти) и выложите куда-нибудь, либо пришлёте на почту (в профиле), могу глянуть, как будет свободное время

Answer 2

[Adamos]

Судоку решается так:
1. проходим по всей таблице и для каждой ячейки определяем, какие цифры в ней могут быть, по уже имеющимся.
2. проходим по всем ячейкам. Если там может быть только одна цифра - заносим эту цифру в ячейки и исключаем ее вариант из всех ячеек, которые "бьет" данная. Выставляем флаг "были изменения".
3. проверяем варианты на всех линиях в поисках единственного места, где может стоять цифра. Если находим такое место - вписываем цифру, "бьем" ячейки, выставляем флаг.
4. если выставлен флаг "были изменения" - возвращаемся в п. 2
5. если поле не заполнено полностью, значит, решения нет.
И никакой перебор с возвратом здесь на хрен не нужен.

Comments

[Vernal96]

а если поле пустое или на нем всего пару цифр написано, то как этот способ подходит?

[Adamos]

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

[Vernal96]

мне важно что бы он находил хотя бы одно решение всегда при любых условиях. Создавать не нужно

[Adamos]

Vernal96: ну, тогда, может быть, и имеет смысл перебор с возвратом.
Хотя я не представляю, зачем это может быть нужно. Время-то в таком переборе растет по экспоненте, а у вас исходных данных - чуть.

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

[Vernal96]

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

[Vernal96]

а рандомом точно ничего не получится найти

[Adamos]

Vernal96: открою вам один секрет судоку: цифры не имеют значения. Если поменять местами все 9 с 1, головомка останется ровно так же однозначно решаемой. Так что при двух цифрах на поле можно вообще сгенерить ЛЮБУЮ готовую судоку и заменить соответствующие цифры.
Если они одинаковы, а в готовой - нет (или наоборот), то ее можно повернуть, отзеркалить, переставить тройки столбцов или строк - и получить нужное попадание.

[Vernal96]

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

[Adamos]

Vernal96: экспоненциальная зависимость - от количества цифр, которые нужно найти. У каждой следующей - от 1 до 8 вариантов. Но в судоку всего 81 цифра, так что это, конечно, не страшно при нынешних мощностях.