Судоку Солвер от Backtracking не работает

Question

Предполагая, что двумерный массив, содержащий сетку судоку 9x9, где моя функция решения ломается? Я пытаюсь решить эту проблему, используя простой подход отслеживания. Спасибо!

bool solve(int grid[9][9])
{
 int i,j,k;
 bool isSolved = false;

  if(!isSolved(grid))
   isSolved = false;

  if(isSolved)
   return isSolved;

  for(i=0; i<9; i++)
  {
   for(j=0; j<9; j++)
   {
    if(grid[i][j] == 0)
    {
     for(k=1; k<=9; k++)
     {
      if(legalMove(grid,i,j,k))
      {
       grid[i][j] = k;
       isSolved = solve(grid);
       if (isSolved)
        return true;
      }
      grid[i][j] = 0;
     }
     isSolved = false;
    }
   }
  }

return isSolved;
}

Даже после изменения проблем isSolved мое решение, похоже, разбивается на бесконечный цикл. Похоже, я пропустил какой-то базовый шаг, но я не уверен, где и почему. Я смотрел на подобные решения и до сих пор не могу определить проблему. Я просто пытаюсь создать базовый решатель, не нужно идти на эффективность. Спасибо за помощь!

Answer 1

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

bool isSolved = false;

if(!isSolved(grid))
    isSolved = false;

if(isSolved)
    return isSolved;

обратите внимание, что ваша переменная isSolved никогда не может быть установлена ​​в true, следовательно, ваш код

if(isSolved)
    return isSolved;

не имеет значения.

Даже если вы исправите это, он будет ощущаться как бесконечный цикл, даже если он конечен. Это связано с тем, что ваш алгоритм может проверять 9 * 9 * 9 = 729 случаев каждый раз, когда он вызывает решение. Ввод этой функции n раз может потребовать проверки до 729 ^ n случаев. Он не будет проверять так много случаев, очевидно, потому что он найдет тупики, когда размещение незаконно, но кто скажет, что 90% от возможных возможных чисел приводят к случаям, когда все, кроме одного числа, соответствуют закону? Более того, даже если бы вы в среднем проверяли k случаев, где k - небольшое число (k <= 10), это все равно взорвалось бы (время выполнения k ^ n.) </p>

Хитрость заключается в том, чтобы «попробовать» размещать числа там, где они, вероятно, приведут к высокой вероятности того, что это будет действительно хорошее размещение. Наверное, самый простой способ сделать это - решить проблему удовлетворения ограничений или использовать алгоритм поиска с эвристикой (например, A *.)

.

На самом деле я написал решатель судоку, основанный на решателе удовлетворения ограничений, и он решил бы 100x100 судоку менее чем за секунду.

Если каким-то чудом алгоритм обратного отслеживания "грубой силы" работает хорошо для вас в случае 9x9, попробуйте более высокие значения, вы быстро увидите ухудшение во время выполнения.

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

Answer 2

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

Ваши функции должны иметь отличные имена от ваших переменных.

Answer 3

Кажется, что независимо от того, является ли это законным ходом, вы присваиваете квадрату «0» с этим «grid [i] [j] = 0;» линия. Может быть, вы хотели поставить «еще» и ТОГДА «grid [i] [j] = 0;»