[PHP]Skrypt do rozwiązywania sudoku
Ten wpis ma 14 lat. Od tego czasu przeglądarki i narzędzia mogły się zmienić, więc zanim użyjesz kodu, sprawdź go z aktualną dokumentacją.
Jakiś czas temu serwis Allegro.pl zamieścił ogłoszenie o tym, że poszukują programistów PHP. Zadaniem do zrealizowania w drugim etapie było stworzenie skryptu który miał rozwiązać sudoku. Zmierzyłem się z tym zadaniem i powstał skrypt rozwiązujący sudoku, którym zamierzam się podzielić na łamach tego bloga.
Sekcja 1Założenia skryptu
- Skrypt ma rozwiązać sudoku korzystając z danych wejściowych przedstawionych przez Allegro.
- Sudoku ma postać kwadratu o wymiarach 9x9
- Skrypt ma pokazywać czas rozwiązania sudoku oraz ilość kroków potrzebnych do rozwiązania
- Dane wstępne do sudoku są pokazywane jako tablica bezpośrednio w klasie skryptu
Sekcja 2Metody klasy rozwiązującej sudoku
Mając zdefiniowane założenia, można przystąpić do tworzenia metod które mają na celu rozwiązanie naszego sudoku. Szybkość rozwiązywania sudoku będzie zależna od stopnia skomplikowania wzorca sudoku z danymi wstępnymi (tzn. im mniej danych wejściowych - tym skrypt może wolniej przeliczać rozwiązanie).
Sekcja 2.1Tablica z danymi wejściowymi
1 2 3 4 5 6 7 8 9 10 | protected $sudoku = array( 0,6,0,0,2,0,0,4,0, 5,0,0,3,0,0,0,0,0, 0,8,0,0,1,0,0,0,0, 6,0,0,0,0,7,0,0,0, 0,3,7,0,0,0,2,8,0, 0,2,0,8,0,0,0,3,0, 0,0,0,0,0,0,0,0,0, 7,0,0,4,0,0,0,0,1, 0,0,0,0,6,0,0,2,0); |
Sekcja 2.2Metody zwracające wiersz, kolumnę i blok sudoku
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | protected function return_row($cell) { return floor($cell/9); } protected function return_col($cell) { return $cell % 9; } protected function return_block($cell) { return floor($this->return_row($cell)/3)*3 + floor($this->return_col($cell)/3); } |
Metody te mają za zadanie odpowiednio podzielić tablicę wejściową z danymi na mniejsze części (wiersz, kolumnę i blok). Dzięki temu skrypt może sprawniej operować na danych.
Sekcja 2.3Metody sprawdzające czy możliwe jest wstawienie numeru do danego elementu
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | protected function is_possible_row($number, $row, $sudoku) { $possible = TRUE; for($x=0;$x<9;$x++) if($sudoku[$row * 9 + $x] == $number) $possible = FALSE; return $possible; } protected function is_possible_col($number, $col, $sudoku) { $possible = TRUE; for($x=0;$x<9;$x++) if($sudoku[$col + 9 * $x] == $number) $possible = FALSE; return $possible; } protected function is_possible_block($number, $block, $sudoku) { $possible = TRUE; for($x=0;$x<9;$x++) if($sudoku[floor($block / 3) * 27 + $x % 3 + 9 * floor($x / 3) + 3 * ($block % 3)] == $number) $possible = FALSE; return $possible; } protected function is_possible_number($cell, $number, $sudoku) { $row = $this->return_row($cell); $col = $this->return_col($cell); $block = $this->return_block($cell); return $this->is_possible_row($number, $row, $sudoku) and $this->is_possible_col($number, $col, $sudoku) and $this->is_possible_block($number, $block, $sudoku); } |
Powyższe metody sprawdzają czy jest możliwość wstawienia danego numeru do kolejno: wiersza, kolumny, bloku. Metoda is_possible_number jest metodą niejako "sumującą logicznie", czyli jeśli można wstawić numer do danego wiersza i kolumny i bloku to zwraca TRUE, czyli numer jest możliwy do wstawienia.
Sekcja 2.4Metody sprawdzające poprawność numerów w elementach
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | protected function is_correct_row($row, $sudoku) { for($x=0;$x<9;$x++) $row_temp[$x] = $sudoku[$row * 9 + $x]; return count(array_diff(array(1, 2, 3, 4, 5, 6, 7, 8, 9), $row_temp)) == 0; } protected function is_correct_col($col, $sudoku) { for($x=0;$x<9;$x++) $col_temp[$x] = $sudoku[$col + $x * 9]; return count(array_diff(array(1, 2, 3, 4, 5, 6, 7, 8, 9), $col_temp)) == 0; } protected function is_correct_block($block, $sudoku) { for($x=0;$x<9;$x++) $block_temp[$x] = $sudoku[floor($block / 3) * 27 + $x % 3 + 9 * floor($x / 3) + 3 * ($block % 3)]; return count(array_diff(array(1, 2, 3, 4, 5, 6, 7, 8, 9), $block_temp)) == 0; } |
Dzięki tym metodom mamy pewność, że numery się nie powtarzają w danym elemencie.
Sekcja 2.5Metody określające dostępne numery
1 2 3 4 5 6 7 8 9 10 11 12 | protected function determine_possible_values($cell, $sudoku) { $possible = array(); for($x=1;$x<10;$x++) if($this->is_possible_number($cell, $x, $sudoku)) array_unshift($possible, $x); return $possible; } protected function determine_random_possible_value($possible, $cell) { return $possible[$cell][rand(0, count($possible[$cell]) - 1)]; } |
Metody określają możliwe numery do wstawienia w danym miejscu sudoku i generują losowo numer do wstawienia.
Sekcja 2.6Metody uzupełniające sudoku
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | //metoda szuka unikalnych, już wstawionych, numerów do sudoku protected function scan_sudoku_for_unique($sudoku) { for($x=0;$x<81;$x++) if($sudoku[$x]==0) { $possible[$x] = $this->determine_possible_values($x, $sudoku); if(count($possible[$x]) == 0) { return FALSE; break; } } return $possible; } //funkcja usuwa numer ktory już występuje w danym elemencie protected function remove_attempt($attempt_array, $number) { $new_array = array(); for($x=0;$x<count($attempt_array);$x++) if($attempt_array[$x] != $number) array_unshift($new_array, $attempt_array[$x]); return $new_array; } //funkcja drukuje możliwe numery do wstawienia protected function print_possible($possible) { $html = '<table cellspacing="1" cellpadding="2">'; for($x=0;$x<9;$x++) { $html .= '<tr>'; for($y=0;$y<9;$y++) { $values = ''; for($z=0;$z<=count($possible[$x * 9 + $y]);$z++) $values .= $possible[$x * 9 + $y][$z]; $html.= '<td>'.$values.'</td>'; } $html .= '</tr>'; } $html .= '</table>'; return $html; } //generuje następny losowy numer protected function next_random($possible) { $max = 9; for($x=0;$x<81;$x++) if((count($possible[$x])<=$max) and (count($possible[$x])>0)) { $max = count($possible[$x]); $min_choices = $x; } return $min_choices; } |
Sekcja 2.7Metoda sprawdzająca czy sudoku jest rozwiązane
1 2 3 4 5 6 7 8 9 10 | protected function is_solved_sudoku($sudoku) { for($x=0;$x<9;$x++) if(!$this->is_correct_block($x, $sudoku) or !$this->is_correct_row($x, $sudoku) or !$this->is_correct_col($x, $sudoku)) { return FALSE; break; } return TRUE; } |
Sekcja 2.8Metody rozpoczynające rozwiązywanie sudoku oraz wyświetlające rozwiązane sudoku na ekranie
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | public function print_sudoku($sudoku) { $html = '<table cellspacing="1" cellpadding="2">'; for($x=0;$x<9;$x++) { $html .= '<tr>'; for($y = 0; $y <= 8; $y++) $html.= '<td>'.$sudoku[$x * 9 + $y].'</td>'; $html .= '</tr>'; } $html .= '</table>'; return $html; } public function solve() { $start = microtime(); $saved = array(); $saved_sud = array(); while(!$this->is_solved_sudoku($this->sudoku)) { $x+=1; $next_move = $this->scan_sudoku_for_unique($this->sudoku); if($next_move==FALSE) { $next_move = array_pop($saved); $this->sudoku = array_pop($saved_sud); } $what_to_try = $this->next_random($next_move); $attempt = $this->determine_random_possible_value($next_move, $what_to_try); if(count($next_move[$what_to_try])>1) { $next_move[$what_to_try] = $this->remove_attempt($next_move[$what_to_try], $attempt); array_push($saved, $next_move); array_push($saved_sud, $this->sudoku); } $this->sudoku[$what_to_try] = $attempt; } $end = microtime(); $ms_start = explode(' ', $start); $ms_end = explode(' ', $end); $total_time = round(($ms_end[1] - $ms_start[1] + $ms_end[0] - $ms_start[0]), 2); echo 'Sudoku zostało rozwiązane w '.$x.' krokach, w czasie '.$total_time.' sekundy'; echo $this->print_sudoku($this->sudoku); } |
Sekcja 3Podsumowanie
Powyższy skrypt potrafi wygenerować kilka rozwiązań dla danego zestawu danych. Wszystkie metody wyżej wspomniane stanowią ciało klasy o nazwie sudoku. Można je oczywiście zmodyfikować tak, aby przyjmowały dane wejściowe zdefiniowane przez użytkownika, ale na moje potrzeby wystarczyło zdefiniowanie tablicy bezpośrednio w ciele klasy.
Mam nadzieję, że wpis okaże się przydatny i pokaże jak rozwiązywać w sposób przystępny dość skomplikowane zagadki logiczne, jaką niewątpliwie jest rozwiązywanie sudoku.
Na stronie fanów bloga na Facebooku został wspomniany inny sposób na rozwiązywanie sudoku. Sposób się opiera o rozwiązanie bazodanowe Oracle: rozwiązywanie sudoku w Oracle.
Demo z tego artykułu jest dostępne do pobrania stąd: PHP skrypt sudoku
O autorze
