Sudoku generator

Question

I managed to create a Sudoku generator but I'll just go ahead and say that it generates 1 out of 500 tries on average. I'd say that's pretty inefficient and I'd like to ask you for advice on improvements.

Basically what I figured is if I had defined a range of numbers that are possible for each cell, then started selecting random numbers for cells 1 by 1 and removing the respective number from its column, row and "box" ( don't really know how they're called ), then it would magically select appropriate numbers and will be left with only one single possible number for the last cell. Well that wasn't the case, but I thought if I gave it a bunch of more tries it would eventually end up as I planned it and it did, the problem is, as I already said that it is very inefficient.

$loop = true;

while ($loop) {
    $loop = false;
    
    // define and clear array
    $matrix = [];

    // Fill all cells with possible numbers
    for ($x = 1; $x < 10; $x++) {
        for ($y = 1; $y < 10; $y++) {
            for ($z = 1; $z < 10; $z++) {
                $matrix[$y][$x][$z] = $z;
            }
        }
    }
    
    // Start selecting random numbers for each cell from
    // the possible numbers contained in it currently
    for ($x = 1; $x < 10; $x++) {
        for ($y = 1; $y < 10; $y++) {
            
            $keys = array_keys($matrix[$x][$y]);
            
            // if there are no keys this means there are no possible
            // numbers for this cell, which means the generator has 
            // failed => restart
            if(count($keys) == 0){
                $loop = true;
                break 2;
            }
            
            // Set cell number to a random number from the possible
            $matrix[$x][$y] = $matrix[$x][$y][$keys[mt_rand(0, count($keys) - 1)]];
            
            // remove the selected number from the possible numbers for
            // the appropriate column and row
            for ($z = 1; $z < 10; $z ++) {
                if ($z != $y) {
                    unset($matrix[$x][$z][$matrix[$x][$y]]);
                }
                if ($z != $x) {
                    unset($matrix[$z][$y][$matrix[$x][$y]]);
                }
            }

            // Define box's start ($w) and end ($W) X position
            if ($x < 4) {
                $w = 1;
                $W = 4;
            } else if ($x < 7) {
                $w = 4;
                $W = 7;
            } else {
                $w = 7;
                $W = 10;
            }

            // Define box's start ($z) and end ($Z) Y position
            if ($y < 4) {
                $z = 1;
                $Z = 4;
            } else if ($y < 7) {
                $z = 4;
                $Z = 7;
            } else {
                $z = 7;
                $Z = 10;
            }

            // Remove selected number from all cells' possible numbers 
            // in the appropriate 3x3 box
            for (; $w < $W; $w++) {
                for ($z = $Z - 3; $z < $Z; $z++) {
                    if (is_array($matrix[$z][$w])) {
                        unset($matrix[$z][$w][$matrix[$x][$y]]);
                    }
                }
            }
        }
    }
}

And please excuse me for the part where variables are named $z, $Z that doesn't make sense, I just have this obsession about re-using variables that I no longer need, which I know is a bad practice but I do it anyway.

EDIT

I currently discovered that it also produces incorrect puzzles occasionally, debugging to find the reason.

Update: I figured the reason out. It was because of the fact that I was using incorrect coordinates for the removal of the selected number from the respective 3x3 grids, however after putting correct coordinates now, no puzzles are generated, it just goes on forever. I guess I will be deleting this question if I don't find a solution soon.

Answer 1

for ($x = 1; $x < 10; $x++) {
    for ($y = 1; $y < 10; $y++) {
        for ($z = 1; $z < 10; $z++) {
            $matrix[$y][$x][$z] = $z;
        }
    }
}

Why 10? The answer is that you are taking < and started with 1 so to get to 9, you either have to use <= 9 or < 10. The <= 9 notation is more readable in this case, as you don't care about 10.

for ( $x = 1; $x <= 9; $x++) {
    $matrix[$x] = [];
    for ($y = 1; $y <= 9; $y++) {
        $matrix[$x][$y] = range(1, 9);
    }
}

I changed the order from [$y][$x] to [$x][$y]. This allows us to initialize the elements of the first array with arrays of their own. This seems better than relying on PHP to create them implicitly when used.

I replaced the innermost for loop with range, but this changes the third dimension to be 0-indexed. We'll have to make changes later.

        $keys = array_keys($matrix[$x][$y]);

        // if there are no keys this means there are no possible
        // numbers for this cell, which means the generator has 
        // failed => restart
        if(count($keys) == 0){
            $loop = true;
            break 2;
        }

        // Set cell number to a random number from the possible
        $matrix[$x][$y] = $matrix[$x][$y][$keys[mt_rand(0, count($keys) - 1)]];

We can make this code even simpler though:

        $keys = array_keys($matrix[$x][$y]);

        // if there are no keys this means there are no possible
        // numbers for this cell, which means the generator has 
        // failed => restart
        if(count($keys) == 0){
             continue 3;
        }

        // Set cell number to a random number from the possible
        $matrix[$x][$y] = $matrix[$x][$y][$keys[mt_rand(0, $possibility_count - 1)]];
        $index = $matrix[$x][$y]-1;

I changed the break 2 to a continue 3, as it seemed more directly what you are trying to do: restart the outer loop.

I also added $index to store the 0-based index of that value. We'll replace later uses of $matrix[$x][$y] with it.

        for ($z = 1; $z < 10; $z ++) {
            if ($z != $y) {
                unset($matrix[$x][$z][$matrix[$x][$y]]);
            }
            if ($z != $x) {
                unset($matrix[$z][$y][$matrix[$x][$y]]);
            }
        }

You're missing some logic in this. Note that $matrix[$x][$z] and $matrix[$z][$y] may not be arrays. We should check that first:

        for ( $z = 1; $z <= 9; $z ++ ) {
            if (  is_array($matrix[$x][$z]) ) {
                unset($matrix[$x][$z][$index]);
            }
            if ( is_array($matrix[$z][$y]) ) {
                unset($matrix[$z][$y][$index]);
            }
        }

We no longer need to check that we aren't at the current point in the $matrix, as the is_array check will drop us out in that case. Also, this uses $index now.

        if ($x < 4) {
            $w = 1;
            $W = 4;
        } else if ($x < 7) {
            $w = 4;
            $W = 7;
        } else {
            $w = 7;
            $W = 10;
        }

This would be easier to follow if you made the second values inclusive:

        if ( $x <= 3 ) {
            $w = 1;
            $W = 3;
        } else if ( $x <= 6 ) {
            $w = 4;
            $W = 6;
        } else {
            $w = 7;
            $W = 9;
        }

Now we have 1-3, 4-6, 7-9. No overlap. After we do the same for $y, we need to adjust the code that uses this:

        for (; $w < $W; $w++) {
            for ($z = $Z - 3; $z < $Z; $z++) {
                if (is_array($matrix[$z][$w])) {
                    unset($matrix[$z][$w][$matrix[$x][$y]]);
                }
            }
        }

to

        for ( ; $w <= $W; $w++ ) {
            for ( ; $z <= $Z; $z++ ) {
                if ( is_array($matrix[$z][$w]) ) {
                    unset($matrix[$z][$w][$index]);
                }
            }
        }

The $z = $Z - 2 is unnecessary, as we already set the initial value of $z.

Note that $w and $W are based on the value of $x while $z and $Z are based on $y. So this means that $matrix[$x][$y] should become $matrix[$w][$z]. In the second loop, you use $matrix[$x][$y] elsewhere. You do it the other way in the first loop, but $w and $z are in the second loop.

        for ( ; $w <= $W; $w++ ) {
            for ( ; $z <= $Z; $z++ ) {
                if ( is_array($matrix[$w][$z]) ) {
                    unset($matrix[$w][$z][$index]);
                }
            }
        }

The complete code is now

while ( true ) {
    // define and clear array
    $matrix = array();

    // Fill all cells with possible numbers
    for ($x = 1; $x <= 9; $x++) {
        $matrix[$x] = array();
        for ($y = 1; $y <= 9; $y++) {
            $matrix[$x][$y] = range(1, 9);
        }
    }

    // Start selecting random numbers for each cell from
    // the possible numbers contained in it currently
    for ($x = 1; $x <= 9; $x++) {
        for ($y = 1; $y <= 9; $y++) {

            $keys = array_keys($matrix[$x][$y]);

            // if there are no keys this means there are no possible
            // numbers for this cell, which means the generator has 
            // failed => restart
            if(count($keys) == 0){
                continue 3;
            }

            // Set cell number to a random number from the possible
            $matrix[$x][$y] = $matrix[$x][$y][$keys[mt_rand(0, count($keys) - 1)]];
            $index = $matrix[$x][$y]-1;

            // remove the selected number from the possible numbers for
            // the appropriate column and row
            for ($z = 1; $z <= 9; $z ++) {
                if ( is_array($matrix[$x][$z]) ) {
                    unset($matrix[$x][$z][$index]);
                }
                if ( is_array($matrix[$z][$y]) ) {
                    unset($matrix[$z][$y][$index]);
                }
            }

            // Define box's start ($w) and end ($W) X position
            if ( $x <= 3 ) {
                $w = 1;
                $W = 3;
            } else if ( $x <= 6 ) {
                $w = 4;
                $W = 6;
            } else {
                $w = 7;
                $W = 9;
            }

            // Define box's start ($z) and end ($Z) Y position
            if ( $y <= 3 ) {
                $z = 1;
                $Z = 3;
            } else if ( $y <= 6 ) {
                $z = 4;
                $Z = 6;
            } else {
                $z = 7;
                $Z = 9;
            }

            // Remove selected number from all cells' possible numbers 
            // in the appropriate 3x3 box
            for ( ; $w <= $W; $w++ ) {
                for ( ; $z <= $Z; $z++ ) {
                    if (is_array($matrix[$w][$z])) {
                        unset($matrix[$w][$z][$index]);
                    }
                }
            }
        }
    }

    break;
}

I also changed the loop control a bit. Rather than track a $loop variable, I use continue in the middle of the loop to bypass the break at the end.

Note that this is a completed Sudoku board. Usually when we talk about Sudoku generators, we're talking about incomplete boards that are ready for play.

Answer 2

Have you considered using real words as your variable names? for example: $Row, $Column and $NumberToTry.

Just because the compiler does not need to know what you are doing it doesn't mean you have to work half blind. Might make reading it in 20 years easier too ;-).

I was just looking for something to create some nice, well structured 'doku paterns and found your post 4 times now. I have a feeling I will shape my own as there is not much sweet examples about. I see this was 2015 or before so suspect you have moved on!