Понимание этой функции C

Question

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

Протестировал функцию и она генерирует действительную сетку Латинского квадрата (Судоку) 9x9. Моя проблема в том, что я не могу понять, как работает функция, я знаю, что структура состоит из целых чисел, p и b, p будет содержать номер ячейки в таблице, но после этого я не понимаю, почему он создает больше массивов (tab 1 и tab2) и как он проверяет латинский квадрат = / etc, суммируя, я полностью потерян.

Я не прошу построчное объяснение, общую концепцию этой функции. очень помог бы мне!

Еще раз спасибо <3 </p>

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;
}

EDIT Отлично, теперь я понимаю структуру, спасибо ответу Лицзе. То, что я до сих пор не понимаю, это часть, которая проверяет значения в случайном порядке). Я не понимаю, как он проверяет, действительно ли случайное размещение значений, без вызова части кода, которая проверяет, является ли движение законным, а также, после размещения случайных чисел, необходимо ли проверять, является ли сетка снова действительной? -

Answer 1

По существу, вызов функции заполняет позиции в и после '(x, y) в таблице tabla, и функция предполагает, что позиции «до» (x, y) заполнены, и возвращает ли возможно законное «заполнение» значений.

Плата линеаризуется путем увеличения x, затем y.

Первая часть функции находит допустимые значения на (x, y), а вторая часть проверяет значения в случайном порядке и пытается заполнить оставшуюся часть доски с помощью рекурсивного вызова.

На самом деле нет смысла иметь tab2, потому что tab может быть многократно использован для этой цели, и функция теряет память (поскольку это никогда не free d, но, помимо этого, это работает).

Имеет ли это смысл для вас?

EDIT

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

EDIT

Обратите внимание, что случайность применяется только к действительным значениям (порядок выбора значений рандомизирован, а не сами значения).

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

Answer 2

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

Базовый подход - это то, что послужило основой для большого количества «Искусственного интеллекта», по крайней мере, как это было видно примерно до конца80-е годы.Самое общее решение многих загадок - это, в основном, попытаться найти все возможные решения.

Итак, сначала вы попробуете все возможные решения с 1 в верхнем левом углу, затем все возможные решения с 2 в верхнем -левый угол и тд.Вы повторяете, чтобы попробовать варианты для второй позиции, третьей позиции и так далее.Это называется исчерпывающим поиском - или «грубой силой».

Проблема в том, что это занимает почти всегда - но вы можете сократить многие бессмысленные поиски.

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

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

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

Уровень сложности сложен, поскольку зависит от восприятия человеком сложности.Хммм - могу ли я где-нибудь снова вставить «трудный» туда ...

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

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

Answer 3

Попробуйте решить судоку самостоятельно, и вы увидите, что в поиске решения есть неотъемлемая рекурсия.Итак, у вас есть функция, которая вызывает себя до тех пор, пока не будет решена вся плата.

Что касается кода, он может быть значительно упрощен, но будет лучше, если вы попытаетесь написать его самостоятельно.* РЕДАКТИРОВАТЬ:

Здесь это один из Java, может быть, это будет похоже на то, что вы пытаетесь сделать.