php easy sudoku solver using backtracking

Question

Недавно я хотел посмотреть, смогу ли я решить легкую судоку (сначала) в php. Я знаю, что php на самом деле не является выбором для программирования, но я знаю, что php лучший, и у меня были проблемы с дизайном в java и c. Тем не менее, я не вижу причин, почему это не должно работать.

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

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

алгоритм выглядит следующим образом:

$cell; // 1-81 - as parameter of the recursive function solve() 
$value; // 1-9 - as parameter ... 

class Sudoku { 

function solve($cell = 1, $value = 1) { 

    // skipping values 

    if the current cell is fix: 

     return solve(cell++, $value); 

    // testing values (logic) 

    if not: 

     if the value is within the square (3x3) itself: 

      return solve($cell, $value++); 

     if the value is within the row: 

      return solve($cell, $value++); 

     if the value is within the col: 

      return solve($cell, value++); 

     if the value is bigger than 9: 

      return solve($cell--, $value_prev); 

     // all test passed, add the new value to list 
     $this->values[$cell] = $value; 

     if all fields are filled: 
      return; 

     if there are fields left: 
      return solve($cell++, 1); 
} 
} 

Если я создаю пустой судоку будет заполнить все правильно до ячейки 43. Там сценарий аварий с фатальной ошибки: фатальная ошибка: Разрешенные размер памяти 134217728 байт исчерпан (пытался выделить 261904 байта).

значения заполняются так:

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 1 2 3
7 8 9 | 1 2 3 | 4 5 6
2 1 4 | 3 6 5 | 8 9 7
3 6 5 | 2 1 4 | , , ,

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

Наконец, я хочу сказать, что я не против лучших решений, но я просто хочу, чтобы это сработало. Если вы не можете дать мне ответ, основанный на этом вы можете посмотреть на файл PHP:

sudoku.php

Edit: sudoku2.php

Спасибо заранее.

Answer 1

Это ваша главная проблема:

if the value is bigger than 9: 
    return solve($cell--, $value_prev); 

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

E.g. вы можете сделать solve return TRUE, если он завершен, или FALSE, если у него закончились варианты. Затем в любое время, когда вы вызываете solve рекурсивно, если он возвращает TRUE, вы возвращаете TRUE, и если он возвращает FALSE, вы вызываете его снова с $value++.