Sudoku Solver алгоритм грубой силы

Question

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

Я использую алгоритм грубой силы - я начинаю с квадратного (или [0] [0], если вы предпочитаете) и вставляете первое юридическое значение. Затем я делаю рекурсивный вызов на следующий квадрат и так далее. Если моя функция не прошла через всю доску и обнаруживает, что нет допустимых правовых значений, она перемещается к предыдущему квадрату и пытается увеличить значение там. Если это не удастся, оно движется дальше. Если он заканчивается на квадратном, без возможных решений, он выходит.

Я признаю, что мой код не очень и, вероятно, довольно неэффективен, но, пожалуйста, имейте в виду, что я студент первого курса, который пытается изо всех сил. Я не возражаю комментарии о том, как effectivize моего кода, хотя :)

Для квадратов без окончательного заданного количества, вот функция решатель:

public void fillRemainderOfBoard(Square sender){ 

    try { 

     while(true){ 
      if(currentPos > boardDimension){ 
       if(previous != null){ 
        this.setNumrep(-1); 
        this.setCurrentPos(1); 
        previous.setCurrentPos(previous.getCurrentPos()+1); 
        previous.fillRemainderOfBoard(this); 
        return; 
       } else if(sender == this){ 
        this.setCurrentPos(1); 
       } else { 
        break; 
       } 
      } 
      if((thisBox.hasNumber(currentPos)) || (thisRow.hasNumber(currentPos)) || (thisColumn.hasNumber(currentPos))){ 
       currentPos++; 
      } else { 
       this.setNumrep(currentPos); 
       currentPos++; 
       break; 
      } 
     } 

     if(this != last){ 
      next.setNumrep(-1); 
      next.fillRemainderOfBoard(this); 
     } else { 

      return; 
     } 
    } catch (StackOverflowError e){ 
     return; 
    } 
} 

В моем коде значение numrep этого значения, квадрат представляет на доске. CurrentPos-переменная - это счетчик, начинающийся с 1 и возрастающий до тех пор, пока он не достигнет юридического значения для представляемого квадрата.

Для квадратов с определенным числом, здесь та же функция:

public void fillRemainderOfBoard(Square sender){ 
    if((sender.equals(this) || sender.equals(previous)) && this != last){ 
     System.out.println(next); 
     next.fillRemainderOfBoard(this); 
    } else if (sender.equals(next) && this != first) { 
     previous.fillRemainderOfBoard(this); 
    } else { 
     System.out.println("No possible solutions for this board."); 
    } 
} 

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

Любая помощь очень ценится! Не стесняйтесь выбирать и мой код; Я все еще участвую (о, разве мы не всегда?).

__ _ __ _ __ _ __ _ __ _ ____EDIT_ __ _ __ _ __ _ __ _ __ _

Благодаря Piotr, который придумал хорошую идею о возврате, я переписал свой код. Тем не менее, я до сих пор не могу заставить его решить любую судоку вообще. Даже с пустой доской, он получает квадрат номер 39, а затем возвращает false полностью назад. Вот мой текущий код:

public boolean fillInnRemainingOfBoard(Square sender){ 
    if(this instanceof SquarePredef && next != null){ 
     return next.fillInnRemainingOfBoard(this); 
    } else if (this instanceof SquarePredef && next == null){ 
     return true; 
    } 

    if(this instanceof SquareNoPredef){ 
     currentPos = 1; 
     if(next != null){ 
      System.out.println(this.index); 
      for(; currentPos <= boardDimension; currentPos++){ 
       if((thisBox.hasNumber(currentPos)) || (thisRow.hasNumber(currentPos)) || (thisColumn.hasNumber(currentPos))){ 
        continue; 
       } else { 
        System.out.println("Box has " + currentPos + "? " + thisBox.hasNumber(currentPos)); 
        this.setNumrep(currentPos); 
        System.out.println("Got here, square " + index + " i: " + numrep); 
       } 

       if(next != null && next.fillInnRemainingOfBoard(this)){ 
        System.out.println("Returnerer true"); 
        return true; 
       } else { 

       } 
      } 
     } 
     if(next == null){ 
      return true; 
     } 
    } 
    System.out.println("Returning false. Square: " + index + " currentPos: " + currentPos); 
    return false; 
} 

Мне пришлось кое-что усложнить, потому что мне нужно было проверить, является ли текущий объект последним. Следовательно, дополнительные, если тесты.О, и причина, по которой я использую boardDimension, заключается в том, что этот решатель sudoku разрешит любую судоку - не только эти 9 на 9 sudokus :)

Можете ли вы определить мою ошибку? Любая помощь приветствуется!

Answer 1

Так что ваша проблема лежит здесь:

previous.fillRemainderOfBoard(this);

и здесь

next.fillRemainderOfBoard(this);

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

boolean fillRemainderOfBoard(Square sender){ 
if (num_defined_on_start) { 
    return next.fillRemainderOfBoard(this); 
} else { 
    for (i = 1; i < 9; ++i) { 
    if (setting i a legal_move) 
     this.setCurrentPos(i); 
    else 
     continue; 
    if (next.fillRemainderOfBoard(this)) 
     return true; 
    } 
    return false; 
} 

Размер стека будет ~ 81.