Вложенные циклы неожиданно вспыхивают

Question

Я пытаюсь создать игру судоку для тех, кто не знает, что это такое. У вас есть поле 9x9, которое должно быть заполнено числами от 1 до 9, каждое число должно быть уникальным в своей строке и столбце, а также в найденном поле 3x3. Я закончил делать циклы внутри двухмерного массива.

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

Я ожидал, по крайней мере, исключение переполнения стека.

Вот мой код:

public class Engine
{
    public int[,] Create()
    {
        int[,] outer = new int[9, 9];


        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                 outer[i, j] = GetRandom(GetUsed(outer, i, j));
            }
        }

        return outer;

    }

    List<int> GetUsed(int[,] arr, int x, int y)
    {
        List<int> usedNums = new List<int>();
        for (int i = 0; i < 9; i++)
        {
            if (arr[x, i] != 0 && i != y)
            {
                if(!usedNums.Contains(arr[x, i]))
                    usedNums.Add(arr[x, i]);
            }
        }

        for (int i = 0; i < 9; i++)
        {
            if (arr[i, y] != 0 && i != x)
            {
                if (!usedNums.Contains(arr[i, y]))
                    usedNums.Add(arr[i, y]);
            }
        }

        int x2 = 9 - (x + 1);
        int y2 = 9 - (y + 1);

        if (x2 <= 3)
            x2 = 2;
        else if (x2 > 3 && x2 <= 6)
            x2 = 5;
        else x2 = 8;

        if (y2 <= 3)
            y2 = 2;
        else if (y2 > 3 && y2 <= 6)
            y2 = 5;
        else y2 = 8;

        for (int i = x2 - 2; i < x2; i++)
        {
            for (int j = y2 - 2; j < y2; j++)
            {
                if (arr[i, j] != 0 && i != x && j != y)
                {
                    if (!usedNums.Contains(arr[i, j]))
                        usedNums.Add(arr[i, j]);
                }
            }
        }

        return usedNums;
    }

    int GetRandom(List<int> numbers)
    {
        Random r;
        int newNum;
        do
        {
            r = new Random();
            newNum = r.Next(1, 10);
        } while (numbers.Contains(newNum));

        return newNum;
    }

}

Answer 1

Это не прорыв , это застревание в бесконечном цикле.

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

Затем, когда вы попытаетесь выбрать случайное значение для некоторого квадрата, внутренняя функция GetRandom будет просто бесконечно зацикливаться, пытаясь выбрать число (так как getUsed уже будет иметь все 1 - 9, do..while никогда не выйдет)

Простой способ убедиться в этом: добавьте это вверху вашей GetRandom функции:

if (Enumerable.Range(1, 9).All(i => numbers.Contains(i)))
    Console.WriteLine("PROBLEM!");

Теперь, если у numbers есть все от 1 до 9, это скажет вам. (А затем продолжайте застрять в бесконечном цикле, но теперь это ваша проблема;))

Кроме того, просто, как sidenote, не следует продолжать делать new Random() объекты, подобные этому; лучше просто иметь один экземпляр Random, инициализировать его в конструкторе и затем продолжать использовать Random.Next. По крайней мере, Random r = new Random() вверху функции, а затем просто r.Next внутри цикла.

Хорошо, вот очень простой пример попадания в неразрешимую позицию, только в первых двух строках:

123|456|789
456|123|X

Не осталось действительного числа, чтобы поставить его в положение, помеченное X - посмотрите, как это произошло?
Заполнение сетки случайными неиспользуемыми числами - это не то же самое, что заполнение ее «ответами» - подумайте об этом, если вы взяли обычную игру судоку и попытались решить , просто поставив любое случайное число это удовлетворяло правилам в каждом пустом квадрате - вы застряли бы довольно скоро, верно? Это именно то, что происходит с вашей программой.

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

Answer 2

Я настроил GetRandom для производительности

static int GetRandom(List<int> usedNums)
{
    List<int> missingNums = new List<int>();
    for (int i = 1; i <= 10; i++)
    {
        if (!usedNums.Contains(i))
            missingNums.Add(i);
    }

    Random r = new Random();
    int rMissingNumIndex = r.Next(0, missingNums.Count - 1);

    return missingNums[rMissingNumIndex];
}

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

Answer 3

Что бы произошло, если бы в GetRandom ваш список numbers был уже заполнен 1-10?

Я думаю, что ваша программа зависает в методе GetRandom, потому что вы велите ей бесконечно повторять цикл, пока она не найдет число от 1 до 10, которого нет в списке.

Вы должны сказать ему искать 0 до 9 , предполагая, что 0 "пусто", и позволяя ему уйти, если он получает 0, потому что на доске имеет значение только 1-9. Кажется, что 0 будет в списке по умолчанию, поэтому просто проигнорируйте его.

do
{
   r = new Random();
   newNum = r.Next(0, 9);
} while (numbers.Contains(newNum) && newNum != 0);

Сделайте снимок и посмотрите, работает ли он!