Генерация случайного латинского квадрата непрерывного цикла

Question

Я работаю над программой для генерации случайных сеток, латинских квадратов и судоку.Я работаю над латинскими квадратами, и все это работает, за исключением того, что я в непрерывном цикле.Если я разобью их, они будут работать нормально.Вероятно, есть что-то маленькое, что я делаю неправильно, и я не могу его найти.Можете ли вы определить, что не так?

РЕДАКТИРОВАТЬ: Для тех, кто не знает, что такое Латинский квадрат (если кто-то не знает), это обычно сетка 9x9, которая не имеет повторов ни в строках, ни в столбцах.

ОБНОВЛЕНИЕ: Я обнаружил проблему с notSame, равным true прямо перед оператором if (notSame).Это всегда равнялось истине, поэтому не заканчивал проверять строку.Теперь, когда я запускаю его, он больше не находится в непрерывном цикле, а вместо этого у строк нет повторений, но столбцы по-прежнему работают.

ОБНОВЛЕНИЕ № 2: Теперь я переделал большую часть кода для столбцов.Мой профессор попросил меня кое-что изменить, но он все еще переводит меня в непрерывный цикл.

int row = 0, col = 0, count = 0;
bool notSame = true;
// setting up rows and columns
for (row = 0; row < grid.GetLength(0); row++)
{
   for (col = 0; col < grid.GetLength(1); col++)
   {

       grid[row, col] = rnd.Next(1, 10);

       //for loop to check rows for repeats
       for (int c = 0; c < col; c++)
       {
           // if there is repeat go back a column and set bool = false
           if (grid[row, col] == grid[row, c])
           {
               col--;
               count++;
               notSame = false;
               break;
            }

            //notSame = true;
        }

     // if bool = true loop to check columns for repeats
     if (notSame)
     {

         for (int r = 0; r < row; r++)
         {
         // if repeat then go back row
            if (grid[row, col] == grid[r, col])
            {
                notSame = false;
                count++;
                break;
             }

          }
          if (notSame == false && count <= 50)
          {
               row--;
               //break;
          }
          else if (notSame == false && count > 50)
          {
               count = 0;
               col = 0;
               row = 0;
               break;
          }
      }
   }
}

Я использую двумерный массив с именем grid.

Answer 1

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

grid[row, col] = rnd.Next(1, 10);

   //for loop to check rows for repeats
   for (int c = 0; c < col; c++)
   {
       // if there is repeat go back a column and set bool = false
       if (grid[row, col] == grid[row, c])
       {
           col--;
           count++;
           notSame = false;
           break;
        }

        //notSame = true;
    }

Счетчик ++ будет увеличиваться и время от времени будет заканчиваться> = 50, что приведет к следующему коду:

 else if (notSame == false && count > 50)
      {
           count = 0;
           col = 0;
           row = 0;
           break;
      }

, что приведет к тому, что все будет сброшенодо 0 и будет перезапущен.Следовательно, это вызвало бесконечный цикл.Спасибо всем за помощь!

Answer 2

Я не знаю, где ваша ошибка кодирования.Но ваш алгоритм не очень эффективен.

И латинские квадраты, и судоку на самом деле являются частными случаями проблемы «раскраски графа».То есть, учитывая группу «узлов», которые произвольно «соединены» вместе, найдите способ окрасить каждый узел так, чтобы ни у двух соединенных узлов не было одинакового цвета.в целом довольно сложно решить быстро, но для конкретных случаев судоку и латинских квадратов это довольно просто и может быть легко сделано в C #.Вы создаете «граф», который имеет 81 узел, и каждый узел «связан» с другими узлами в своей строке и столбце.«Цвета» - это числа от 1 до 9.

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

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

Answer 3

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

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

Который легко генерировать для любого размера с помощью циклических перестановок строк, а затем просто присваивать каждое значение в сетке (1,2,3,4) другому, сгенерированному случайным образом. Например, вы можете просто перемешать список чисел 1,2,3,4 и получить, скажем, 2,4,3,1. Теперь просто замените 1 на вашем квадрате первой записью в вашем перетасованном списке, 2 на второй и так далее, чтобы получить:

2 4 3 1
4 3 1 2
3 1 2 4 
1 2 4 3

Теперь вы также можете перетасовать порядок строк (и / или столбцов), если хотите, и он все еще должен быть действительным.

Редактировать: на самом деле, подумав об этом, вероятно, проще всего начать с первого квадрата, а затем перетасовать столбцы и строки. Нет необходимости выполнять замену.

Answer 4

делает явное уменьшение переменной, с которой вы перебираете, - это нет, нет. это, вероятно, ваша проблема. Это звучит как хорошее место, чтобы вернуться назад, чтобы избежать этого:)

РЕДАКТИРОВАТЬ: я видел, видел много проблем, я не знаю, с чего начать. Этот алгоритм никогда не даст вам то, что вам нужно. Прежде всего, это может привести к проблеме взаимоблокировки, когда вы начнете заполнять ее, и вы не сможете добавить число к определенной строке / столбцу. Представьте, что у вас есть 12345 в строке 5, а затем в столбце 6. числа 6 7 8 9 .. ну, вы не можете добавить номер в строку 5, столбец 6;) увидеть проблему там ?? кроме того, у вашего кода есть несколько проблем: изменение переменных итерации во время итерации является большой проблемой, и ее следует избегать.

один раз notSame = false; тогда так и останется до конца вашей казни.

столбцы идут по вертикали, а строки по горизонтали, так что это (1,2) - это столбец строки 1, 2 ... вы проверяете строки на первом этапе .. и столбцы на втором ..

// if bool = true loop to check columns for repeats
     if (notSame)
     {

         for (int r = 0; r < row; r++)
         {
             // if repeat then genereate new random and go back row
             if (grid[row, col] == grid[r , col])
             {
                 grid[row, col] = rnd.Next(1, 10);

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

скажу своему учителю, чтобы он пришел сюда и прочитал это;) .. Я не знаю, как еще вам помочь, этот алгоритм совершенно неверен и требует полного рефакторинга (и да, вы можете сделать это, используя итерацию, но не для, вам нужно использовать while и flags).