4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Why not do the checks as you're filling cells? Check row/column/square to see if the value exists, and if it does reroll(and add that to a list so you don't have to recheck same values). Square can be a little tricky, but doing the checks as you insert guarantees that you will have a complete puzzle at the end. \$\endgroup\$ – Demarini Jan 13 '15 at 22:01
  • \$\begingroup\$ @Demarini I remember this was my idea when I tried to create such generator in the past but then the problem was that it would meet such cases in which there are no numbers available to add (actually the same problem I'm having now). Essentially that's what I've done now with the exception that I first add numbers and then pick. \$\endgroup\$ – php_nub_qq Jan 13 '15 at 22:09
  • \$\begingroup\$ Check out this previous answer of mine, about generating a Sudoku: codereview.stackexchange.com/a/49391/31562 \$\endgroup\$ – Simon Forsberg Jan 13 '15 at 22:19
  • \$\begingroup\$ Also take a look at this Stack Overflow answer, which is essentially what I would write in a review: stackoverflow.com/a/7280517/1310566 . And this one: stackoverflow.com/a/6925745/1310566 (this one is a really good suggestion) \$\endgroup\$ – Simon Forsberg Jan 13 '15 at 22:21
4
\$\begingroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ What is this sorcery? Firstly I'd like to thank you for the review, it is quite descriptive and helpful. But then I couldn't help but wonder, what made your version generate puzzles when it is basically the same thing ( logically ), since mine failed? In addition, when I hand out the puzzle I remove a certain amount of cells according to the difficulty the user selected. \$\endgroup\$ – php_nub_qq Jan 14 '15 at 7:40
  • \$\begingroup\$ @php_nub_qq It's the $matrix[$z][$w], which should be $matrix[$w][$z] both places that it is used. \$\endgroup\$ – Brythan Jan 15 '15 at 2:00
  • \$\begingroup\$ But this doesn't make sense. In the $matrix the first index is the row and the second is the column, having $w represent column and $z row it makes sense to be $matrix[$z][$w]. In addition, why did you remove my edit? This way it only iterates through 1 row of the 3x3 grid, not checking the remaining two? \$\endgroup\$ – php_nub_qq Jan 15 '15 at 7:28
  • \$\begingroup\$ @php_nub_qq I don't know about rows vs. columns, as this code does not display the board. What I do know is that in the second loop, you say $matrix[$x][$y], that $w is derived from $x and $z from $y, and that you are using $matrix[$z][$w] which does not match. As a general rule, I would argue that the second index should come from the inner loop. For that reason, I changed the order in the first pair of nested loops. And in the $w/$z loops. \$\endgroup\$ – Brythan Jan 15 '15 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.