Исходники судоку

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

Что касается алгоритма, то здесь все работает так. У нас есть поле 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.

Leave a Reply

Your email address will not be published. Required fields are marked *