Backtracking algorithm to generate a sudoku grid does not complete

Question

I wrote a sudoku generator that creates numbers cell by cell and checks immediately after a cell has been created if it is valid (horizontally, vertically and in a 3x3 block).

Now my problem is that the algorithm always gets stuck at some point, as it won't find a valid number for the current cell. Sometimes closer to the end, sometimes already after writing 30 cells.

This is my function to check the cell, which should change the number depending on its validity:

private function checkCell($index)
{
    while ($this->isValid($index) === false) {

        $this->cell[$index]->setValue(rand(1, 9));
        $this->counter++;

        echo 'counter: ' . $this->counter;
        echo PHP_EOL;

        if ($this->counter > 1000) {
            $this->display();
            die();
        }
    }
}

isValid() checks if the cell is valid horizontally, vertically and in a block (this is currently not working, it just returns true).

The counter is for debugging purposes so I can see when it gets stuck.

Here is the function generating my cells:

private function fillCell($index)
{
    $rand = rand(1, 9);
    $this->cell[$index]->setValue($rand);
    $this->checkCell($index);
}

What should be changed so the algorithm doesn't get stuck all the time?

spenibus spenibus · Accepted Answer · 2015-09-28T17:12:39

The issue might be that the algorithm is a little too random. You end up creating a grid that is invalid and can not be completed further.

I would propose starting from a known valid grid and shuffle the cells randomly. If a cell can't be moved, we can simply skip it.

A fair warning to the reader, the following will contain pseudo code rather than working code.

A perfectly valid starting grid:

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

We can store this in a single dimension array, as you already appear to do.

We follow a simple logic:

We create a single dimension array containing the cells

$cells = array(
    1,2,3,4,5,6,7,8,9,7,8,9,1,2,3,4,5,6,4,5,6,7,8,9,1,2,3,
    9,1,2,3,4,5,6,7,8,6,7,8,9,1,2,3,4,5,3,4,5,6,7,8,9,1,2,
    8,9,1,2,3,4,5,6,7,5,6,7,8,9,1,2,3,4,2,3,4,5,6,7,8,9,1,
);

We create another array containing numbers from 0 to 80 in a random order, which are the indexes of $cells
```
$indexes = range(0, 80);
shuffle($indexes);
```
We iterate over $indexes and use the value to select a random $cell in $cells
```
foreach($indexes as $index) {
    $cell = $cells[$index];
}
```
For each $cell, we iterate over $cells. In each iteration, we create a temporary grid where we switch the value of the current cell with the value of the target cell. If the temporary grid is valid, we save the target index in an array of candidates
```
// pseudo code because that's a lot of work
$candidates = getCandidates($cell, $cells);
```

We randomly choose one of the candidates and switch the cells. If no candidate is available, we simply ignore this step

candidatesCount = count(candidates);
if(candidatesCount > 0) {
    $candidate = $candidates[range(0, candidatesCount -1)];
    // switch values
    $cells[$index]    = $cells[$candidate];
    $cells[candidate] = $cell;
}

Repeat until $cells is processed

There are likely more efficient ways to proceed, but this logic can not get stuck.

Note that there is a low probability that the shuffle will undo itself and produce the original grid. But it's still a valid grid.

Backtracking algorithm to generate a sudoku grid does not complete

2 Answers