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

Это решение для судоку, и каждый квадрат имеет этот метод. Моя идея заключается в том, что если один экземпляр этого метода проходит цикл без поиска допустимых значений, он вернется к предыдущему методу, который вызвал его, и продолжит цикл - пробуя следующее значение из цикла for. Я надеялся, что этого хватит для отступления, но все мои испытания терпят неудачу, и я совершенно не знаю, как я собираюсь решить эту проблему./Конец нуб-плачНевозможно выяснить, как включить обратный трассировку в мой псевдорекурсивный метод.

public boolean recursive() { 

    for(int i = 1; i <= boardSize; i++) { 

     if(!validValue(i)) { 
      continue; 
     } else { 
      setValue(i); 

      if(getNext() == null) // This signifies that I am at the end of the list 
       return true; 
      else 
       getNext().recursive(); // same method in the next sudoku square 
     } 
    } 

    return false; 
}

источник

2012-04-17 jollyroger

Этот код не является достаточным, чтобы увидеть, что происходит. Какова структура алгоритма и что делают 'validValue',' setValue', 'getNext' и' recursive'? Хотя я не могу с уверенностью сказать, что не так, я предполагаю, что вы не отменяете изменения во время обратного отслеживания. Когда поиск не находит решение, он должен сбросить любое постоянное состояние, которое оно изменило перед обратным трассировкой. – Heatsink

Извините, я сделал плохое предположение, думая, что имена методов не требуют пояснений. validValue (i) проверяет, находится ли i в поле box/row/column, которое относится к квадрату. setValue() - это setter для значения в каждом квадрате. getNext() возвращает следующий квадрат на доске sudoku. Я сожалею, что не видел этого, но почему мне нужно сбросить значение, если метод setValue() просто перезапишет любое неправильное значение? – jollyroger

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

Два вопроса корректности здесь:

Вы должны проверить, если результат от рекурсивного invokation был true - и если да, то вы должны остановить рекурсию - вы нашли решение, не отменяйте его!
Вы должны пузыриться возвращаемое значение рекурсии, в частности - если getNext().recursive(); дает true - вы должны пузырек это true вверх [и, как сказано в (1) - остановить рекурсию, у вас есть решение!]

источник

2012-04-17 14:07:17 amit

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

@jollyroger: Он решает проблемы, на которые я обращался - я понятия не имею, будет ли это теперь правильно. Кроме того: я возвращаю код обратно к оригиналу, потому что другие могут учиться у него! Если код все еще не работает, вы должны опубликовать новый вопрос, который описывает, как и почему код выходит из строя. – amit

Благодарим за помощь. – jollyroger

Вы дважды вызываете getNext(). Если он не возвращает значение null в вашем операторе if, вы вызываете его снова. Вы уверены, что хотите это сделать?

источник

2012-04-17 14:09:36 JazzHands

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

После того, как цикл завершен, методу необходимо сбросить его значение. Если бы старые значения, которые ранее были протестированы перед возвратом, остались бы после возврата. Это означало бы, что когда метод isValid() будет проверять столбец, строку и поле, которым принадлежит данный квадрат, метод isValid() найдет множество значений, установленных ранее.

Все, что было нужно, это одна строка, прежде чем «вернуть ложь»;

//(end of for-loop) 
setValue(0); 
return false; 
//(method ends)

источник

2012-04-21 21:20:42 jollyroger

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

ответ

Смежные вопросы