Понимание этой функции C
Я пытаюсь понять, как работает эта функция, я изучил несколько алгоритмов для создания головоломок судоку и выяснил этот.
Протестировал функцию и она генерирует действительную сетку Латинского квадрата (Судоку) 9x9. Моя проблема в том, что я не могу понять, как работает функция, я знаю, что структура состоит из целых чисел, p и b, p будет содержать номер ячейки в таблице, но после этого я не понимаю, почему он создает больше массивов (tab 1 и tab2) и как он проверяет латинский квадрат =/ etc, подводя итог, я полностью потерян.
Я не прошу построчное объяснение, общую концепцию этой функции. помог бы мне много!
Еще раз спасибо <3
int sudoku(struct sudoku tabla[9][9],int x,int y)
{
int tab[9] = {1,1,1,1,1,1,1,1,1};
int i,j;
for(i=0;i<y;++i)
{
tab[tabla[x][i].p-1]=0;
for(i=0;i<x;++i)
{
tab[tabla[i][y].p-1]=0;
}
for(i=(3*(x/3));i<(3*(x/3)+3);++i)
{
for(j=(3*(y/3));j<y;++j)
{
tab[tabla[i][j].p-1]=0;
}
}
int n=0;
for(i=0;i<9;++i)
{
n=n+tab[i];
}
int *tab2;
tab2=(int*)malloc(sizeof(int)*n);
j=0;
for(i=0;i<9;++i)
{ if(tab[i]==1)
{
tab2[j]=i+1;
j++;
}
}
int ny, nx;
if(x==8)
{
ny=y+1;
nx=0;
}
else
{
ny=y;
nx=x+1;
}
while(n>0)
{
int los=rand()%n;
tabla[x][y].p=tab2[los];
tab2[los]=tab2[n-1];
n--;
if(x==8 && y==8)
{
return 1;
}
if (sudoku(tabla,nx,ny)==1)
{
return 1;
}
}
return 0;
}
РЕДАКТИРОВАТЬ Отлично, теперь я понимаю структуру, спасибо ответ Лиджи. То, что я до сих пор не понимаю, это часть, которая проверяет значения в случайном порядке). Я не понимаю, как он проверяет, действительно ли случайное размещение значений, без вызова части кода, которая проверяет, является ли движение законным, а также, после размещения случайных чисел, необходимо ли проверять, является ли сетка снова действительной? -
3 ответа
По сути, вызов функции заполняет позиции в и после (x, y) в таблице tablaи функция предполагает, что позиции "до" (x, y) заполняется и возвращает возможность легального "заполнения" значений.
Плата линеаризуется через увеличение x, затем y.
Первая часть функции определяет допустимые значения (x, y), а вторая часть проверяет значения в случайном порядке и пытается заполнить оставшуюся часть доски с помощью рекурсивного вызова.
Нет никакого смысла в том, чтобы tab2 так как tab может быть повторно использован для этой цели, и функция утечки памяти (так как она никогда не freeг, но кроме них это работает).
Это имеет смысл для вас?
РЕДАКТИРОВАТЬ
Единственная сложная область в части, которая проверяет юридический номер, - это третий цикл (флажок 3x3). Условие для j является j < y потому что те значения, где j == y уже проверены вторым циклом.
EDIT2
Я придираюсь, но та часть, которая имеет значение n и заполняет tab2 с юридическими ценностями действительно должно быть
int n = 0;
for (i = 0; i < 9; ++i) if (tab[i]) tab[n++] = i+1;
следовательно, исключая необходимость tab2 (более поздний код может просто использовать tab а также n вместо tab2). Утечка памяти, таким образом, устранена.
РЕДАКТИРОВАТЬ
Обратите внимание, что случайность применяется только к действительным значениям (порядок выбора значений рандомизирован, а не сами значения).
Код следует стандартному шаблону исчерпывающего поиска: попробуйте каждое возможное значение кандидата, сразу же вернувшись, если поиск завершится успешно, и откат с ошибкой, если все значения кандидата потерпели неудачу.
Краткое описание принципов - игнорирование приведенного вами примера. Надеюсь, с идеей, вы можете связать ее с примером самостоятельно.
Базовый подход - это то, что лежало в основе большого количества "искусственного интеллекта", по крайней мере, как это было видно примерно до конца 80-х годов. Самое общее решение для многих загадок в основном состоит в том, чтобы попробовать все возможные решения.
Итак, сначала вы попробуете все возможные решения с 1 в верхнем левом углу, затем все возможные решения с 2 в верхнем левом углу и так далее. Вы повторяете, чтобы попробовать варианты для второй позиции, третьей позиции и так далее. Это называется исчерпывающим поиском или грубой силой.
Беда в том, что это занимает почти всегда - но вы можете сократить многие бессмысленные поиски.
Например, поместив 1 в верхнем левом углу, вы выполняете рекурсию. Вы помещаете 1 в следующую позицию и снова выполняете рекурс - но теперь вы обнаруживаете, что нарушили два правила (два в ряд, два в блоке 3х3), даже не заполнив остальную часть доски. Таким образом, вы "возвращаетесь назад" - т.е. выходите из рекурсии на предыдущий уровень и переходите к установке 2 на эту вторую позицию.
Это избегает большого количества поиска и делает вещи практичными. Также возможны дальнейшие оптимизации, если вы будете следить за тем, чтобы цифры все еще не использовались в каждой строке, столбце и блоке - подумайте о пересечении этих наборов.
То, что я описал, на самом деле является алгоритмом решения (если вы разрешите заполнение некоторых ячеек). Генерация случайного решенного судоку - это то же самое, но для каждой позиции цифр вы должны пробовать цифры в случайном порядке. Это также оставляет проблему принятия решения о том, какие ячейки оставить пустыми, в то же время гарантируя, что головоломка все еще может быть решена, и (намного сложнее) конструирования головоломок с настройкой уровня сложности. Но, в некотором смысле, основной подход к этим проблемам уже здесь - вы можете проверить, является ли конкретный набор пустых пробелов допустимым, запустив алгоритм решения и найдя, например, (и сколько) решений, которые вы получаете, например, Вы можете создать поиск действительного набора ячеек, оставленных пустыми.
Уровень сложности сложен, потому что зависит от восприятия человеком сложности. Хммм - могу ли я вписать "трудно" туда снова где-то...
Один из подходов - разработать более сложный алгоритм поиска, который использует типичные эмпирические правила, а не рекурсивный поиск, и который оценивает сложность как самый глубокий необходимый уровень рекурсии. Некоторые эмпирические правила также могут быть оценены как более продвинутые, чем другие, поэтому их использование в большей степени ведет к трудностям. Очевидно, что сложность субъективна, поэтому нет единого правильного ответа о том, как именно следует делать подсчет очков.
Это дает вам меру сложности для конкретной головоломки. Создать головоломку напрямую для уровня сложности будет сложно, но при попытке выбора различных ячеек, чтобы оставить поле пустым, вы можете попробовать несколько вариантов, отследить все оценки сложности и в конце выбрать тот, который был ближайшим к вашему. целевой уровень сложности.
Попробуйте решить судоку самостоятельно, и вы увидите, что в поиске решения есть неотъемлемая рекурсия. Итак, у вас есть функция, которая вызывает себя, пока не решена вся плата.
Что касается кода, он может быть значительно упрощен, но будет лучше, если вы попытаетесь написать его самостоятельно.
РЕДАКТИРОВАТЬ:
Вот один из Java, может быть, это будет похоже на то, что вы пытаетесь сделать.