Генерация случайного латинского квадрата непрерывного цикла
Я работаю над программой для генерации случайных сеток, латинских квадратов и судоку. Я работаю над латинскими квадратами, и все это работает, за исключением того, что я в непрерывном цикле. Если я разобью их, они будут работать нормально. Вероятно, есть что-то маленькое, что я делаю неправильно, и я не могу его найти. Можете ли вы определить, что не так?
РЕДАКТИРОВАТЬ: Для тех, кто не знает, что такое латинский квадрат (если кто-то не знает), это обычно сетка 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;
}
}
}
}
Я использую 2D-массив, называемый сеткой.
4 ответа
Моя проблема заключалась в дополнительном подсчете в проверке строк. Счет всегда будет превышать 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 и перезапустится. Следовательно, это вызвало бесконечный цикл. Спасибо всем за помощь!
Я не знаю, где ваша ошибка кодирования. Но ваш алгоритм не очень эффективен.
И латинские квадраты, и судоку на самом деле являются частными случаями проблемы "раскраски графа". То есть, учитывая группу "узлов", которые произвольно "соединены" вместе, найдите способ окрасить каждый узел так, чтобы никакие два соединенных узла не имели одинаковый цвет.
В общем, эту проблему довольно трудно решить быстро, но для конкретных случаев судоку и латинских квадратов это довольно просто и может быть легко решено в C#. Вы создаете "граф", который имеет 81 узел, и каждый узел "связан" с другими узлами в своей строке и столбце. "Цвета" - это числа от 1 до 9.
В моей серии статей из пяти частей я расскажу вам, как создать эффективный алгоритм раскраски графов, который может решить судоку. Было бы не сложно адаптировать алгоритм для генерации судоку.
http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/
Я думаю, что самый простой способ создать латинский квадрат - начать с известного латинского квадрата. Сказать:
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
Теперь вы также можете изменить порядок строк (и / или столбцов), если хотите, и он все еще должен быть действительным.
Изменить: на самом деле, думая об этом, вероятно, проще всего просто начать с первого квадрата, а затем перетасовать столбцы и строки. Нет необходимости делать замену.
Делать явное уменьшение переменной, с которой вы итерируете, - нет, нет. это, вероятно, ваша проблема. Это звучит как хорошее место, чтобы вернуться назад, чтобы избежать этого:)
РЕДАКТИРОВАТЬ: я вижу видел много проблем, я не знаю, с чего начать. Этот алгоритм никогда не даст вам то, что вам нужно. Прежде всего, это может привести к проблеме взаимоблокировки, когда вы начнете заполнять ее, и вы не сможете добавить число к определенной строке / столбцу. Представьте, что у вас есть 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).