I recently wanted to see if I am able to solve an easy sudoku (at first) within php. I know php is not really the choise for programming reasons, but I know php the best and I had problems with the design in java and c. Nonetheless, I don't see any reason why it shouldn't work.

First I don't wanted to ask you, because there were some solved threads out there. But I found that those solutions are too complicated for me to understand (other languages, complex structurs) and out of my aim.

My question is: Can somebody give me a hint based on my aim? I want a simple sudoku solver without guessing, just with backtracking.

The algorithm looks like this:

$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);
}
}

If I create a blank sudoku it will fill up all correctly until cell 43. There the script crashes with an fatal error: Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 261904 bytes).

The values are filled in like:

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 | . . .

I guess there is an infinite loop or something that causes this crash. Maybe it is not solvable like this. I just wanted to know if I am doing right or what I forgot to check. I also tried this algorithm with fixed values from an easy-sudoku. It crashes too ... maybe there is to much backtracking.

Finally, I want to say that I'm not against better solutions but I just want this to work. If you cannot give me an answer based on this you can have a look at the php file:

sudoku.php

Edit: sudoku2.php

Thanks in advance.

• php
• sudoku
• backtracking

This is your main problem:

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

When you get to that point (where nothing works, so you have to go back and change something previously), you can't recurse deeper as you are, because your stack will grow way too big with accumulation of mistakes. You need to actually return back to the previous stack level and keep going from there.

E.g. you might make solve return TRUE if it's complete, or FALSE if it ran out of options. Then any time you call solve recursively, if it returns TRUE, you return TRUE, and if it returns FALSE, you call it again with $value++.