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

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, то вам скажу. (И затем продолжайте застревать в бесконечном цикле, но это ваша проблема сейчас;))

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

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

123|456|789 
456|123|X 

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

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

Answer 2

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

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

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

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

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

Answer 3

я щипнул 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 элементами, что означает, что не может быть никакого решения. Попробуйте использовать этот метод, и вы увидите проблему.