Судоку решатель бесконечный цикл

Я пишу решатель судоку на основе алгоритм обратной трассировки.

Я написал весь класс для решения, и он работает, но только для действительно простых головоломок (например, 5 из 81 номеров отсутствуют). С классической легкой головоломкой (около 40 пропущенных чисел) она выдает ошибку (конкретно фатальная ошибка: допустимый объем памяти 1342177280 байт исчерпан (попытка выделить 65488 байт)). Я думаю, что это бесконечный цикл, но я не могу его найти.

Моя решающая функция работает следующим образом:

Find empty cell
If empty cell request return true, there is no empty cell -> sudoku is solved

If selected cell is empty prepare number 1
If selected cell is not empty, get it's number do +1

Try if prepared number is valid, if not do +1, if tryied number is 9, then start function again and go back

If prepared number was valid, write it into array.

Run this solving function (here probably will be the infinity loop I guess)

Я пытался отладить его с помощью номера die () по номеру, но первые несколько цифр были в порядке, и все шло хорошо.

Где должна быть ошибка?

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

<?php

class sudokuSolver {

private $line = 0;
private $column = 0;

private $sudokuOnlyForRead = array(
array('', '', '6', '4', '7', '', '3', '', ''),
array('', '', '4', '6', '5', '', '9', '', ''),
array('3', '', '', '', '', '8', '', '4', ''),

array('2', '6', '7', '3', '', '9', '5', '', ''),
array('8', '', '', '2', '4', '7', '1', '', ''),
array('', '', '', '', '', '', '', '', '7'),

array('', '', '2', '', '6', '5', '4', '3', '1'),
array('', '', '8', '9', '3', '1', '', '2', ''),
array('', '3', '', '', '', '', '', '', ''),
);

private $sudoku = array(
array('', '', '6', '4', '7', '', '3', '', ''),
array('', '', '4', '6', '5', '', '9', '', ''),
array('3', '', '', '', '', '8', '', '4', ''),

array('2', '6', '7', '3', '', '9', '5', '', ''),
array('8', '', '', '2', '4', '7', '1', '', ''),
array('', '', '', '', '', '', '', '', '7'),

array('', '', '2', '', '6', '5', '4', '3', '1'),
array('', '', '8', '9', '3', '1', '', '2', ''),
array('', '3', '', '', '', '', '', '', ''),
);public function solve()
{
$nextEmptyCell = $this->findNextEmptyCell();

startForLastEmptyCell:

if ($nextEmptyCell === true) {
return $this->sudoku;
}

if (empty($this->getActualCell())) {
$newNumber = 1;
} else {
$newNumber = $this->getActualCell()+1;
}

while ($this->isNewNumberValid($newNumber) == false) {
$newNumber++;

if ($newNumber == 10) {
$this->findLastEmptyCell();
goto startForLastEmptyCell;
}
}

$this->sudoku[$this->line][$this->column] = $newNumber;

$this->solve();
}

private function isValidInLine($number)
{
$searchedLine = $this->line;

if (in_array($number, $this->sudoku[$searchedLine])) {
return false;
}

return true;
}

private function isValidInColumn($number)
{
$searchedColumn = $this->column;

foreach ($this->sudoku as $lines) {
if ($lines[$searchedColumn] == $number) {
return false;
}
}

return true;
}

private function isValidInBox($number)
{
$searchedLine = $this->line;
$searchedColumn = $this->column;

$linesToInspect = $this->coordsToInspectInBox($searchedLine);
$columnsToInspect = $this->coordsToInspectInBox($searchedColumn);

foreach ($linesToInspect as $lineToInspect) {
foreach ($columnsToInspect as $columnToInspect) {
if ($number == $this->sudoku[$lineToInspect][$columnToInspect]) {
return false;
}
}
}

return true;
}

private function isNewNumberValid($number)
{
if ($this->isValidInLine($number) && $this->isValidInColumn($number) && $this->isValidInBox($number)) {
return true;
}

return false;
}

private function findNextEmptyCell()
{
$nextEmptyCell = '';

$searchedLine = $this->line;
$searchedColumn = $this->column;

while(empty($nextEmptyCell)) {

if ($searchedColumn == 9) {
$searchedColumn = 0;
$searchedLine++;
}

if ($searchedLine == 9) {
return true;
}

if(empty($this->sudoku[$searchedLine][$searchedColumn])) {
$nextEmptyCell = array($searchedLine, $searchedColumn);

$this->line = $searchedLine;
$this->column = $searchedColumn;

return $nextEmptyCell;
}

$searchedColumn++;
}
}

private function findLastEmptyCell()
{
$lastEmptyCell = '';

$searchedLine = $this->line;
$searchedColumn = $this->column;

while(empty($lastEmptyCell)) {

if ($searchedColumn == 0) {

$searchedColumn = 8;
--$searchedLine;
}

--$searchedColumn;

if(empty($this->sudokuOnlyForRead[$searchedLine][$searchedColumn])) {

$lastEmptyCell = array($searchedLine, $searchedColumn);

$this->line = $searchedLine;
$this->column = $searchedColumn;
}
}

return $lastEmptyCell;
}

private function coordsToInspectInBox($coord)
{
if ($coord % 3 == 0) {
return array($coord, $coord+1, $coord+2);
} elseif ($coord % 3 == 1) {
return array($coord-1, $coord, $coord+1);
} elseif ($coord % 3 == 2) {
return array($coord-2, $coord-1, $coord);
}
}

private function getActualCell()
{
return $this->sudoku[$this->line][$this->column];
}

}