Я уже давно обещал выложить исходные коды судоку (поиграйте в судоку, если еще не играли). Я думал, что со временем исправлю код, сделаю лучше, но нет ни времени, ни желания. Поэтому лучше я выложу как есть, а вы уж сами улучшайте. Посмотреть код. Далее в посте будут комментарии.

Что касается алгоритма, то здесь все работает так. У нас есть поле 9х9, соответственно начнем мы с

public function generate() {
  $this->error_counter = 0;
  for ($row = 0; $row < 9; $row++) {
    for ($col = 0; $col < 9; $col++) {

$error_counter служит нам для защиты от тупиков. Сейчас вы увидите о чем речь.

if ($this->error_counter > self::retry_after) {
    //Row will be incremented to 0
    $row = -1;
    $col = 0;
    $this->error_counter = 0;
 
    $this->reset();
    break;
}

Если количество ошибок при генерации вышло за определенные пределы - значит звезды сложились неудачно и что-то где-то не сходится. Поэтому генерация сбрасывается и начинается заново.

if ($this->sudoku[$row][$col]->getNum() == 0) {
    //Вычисляем какие цифры подходят в текущую клетку
    $fit = $this->fit($row, $col);
 
    $percents = array();
    foreach (self::$numbers as $number) {
        $percents[$number] = $this->percentage($number, $row, $col, $fit);
    }
 
    //Here we get all numbers, that are most possible
    $available = array();
    $max = max(array_values($percents));
    foreach ($fit as $number) {
        if ($percents[$number] == $max) {
            $available[] = $number;
        }
    }

Вот тут и происходит вся магия. Сначала вычисляем какие числа могут встать в клетку (смотрим, чтобы по вертикали, горизонтали и в малом квадрате такой не было). Далее для каждого из этих чисел запускается мутная функция percentage. Она вычисляет, какой шанс у числа попасть в эту клетку. Допустим у нас осталось 4 свободные клетки и 4 числа. При этом первое число может попасть в 1 клетку из 4х, второе в две, третье в три, четвертое во все. Эта функция просто делит количество клеток куда число может попасть на количество пустых клеток. Таким образом, выпадет число, у которого меньше всего шансов попасть в другие клетки. При равенстве берем случайное.

//It can turn that sudoku generation isn't going well
if (count($available) == 0) {
    foreach ($this->sudoku[$row] as $cell) {
        $cell->setNum(0);
    }
    $row--;
    $this->error_counter++;
    break;
}

В переменной available хранятся те самые числа, которые могут попасть в текущую клетку и имеют наивысшую вероятность попасть. Если вдруг оказывается, что никакое число не может попасть, а ряд еще не закончился - то мы сбрасываем текущий ряд и начинаем генерировать его заново. Ну а если сбрасывается ряд (по умолчанию) 30 раз, тогда, как я уже говорил, перегенерируется вся головоломка.

if ($this->error_counter > self::retry_after) {
    break;
}
$this->sudoku[$row][$col]->setNum($available[mt_rand(0, count($available)-1)]);

Тут все просто, если надо сбросить головоломку - идем в начало и сбрасываем. А если все в порядке - берем случайное число, если их несколько.
Ну а все остальное по-моему достаточно просто и понятно.

That's all folks.

А еще я писал про:

1. Как проверить существует ли сайт
2. Symfony: динамический роутинг
3. PHP: Получить строку по номеру