chevron-left chevron-right

[PHP]Skrypt do rozwiązywania sudoku

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.

Założenia skryptu

Sudoku do rozwiązania
  • 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

Metody 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).

Tablica 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);

Metody 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.

Metody 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.

Metody 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.

Metody 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.

Metody 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;
}

Metoda 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;
}

Metody 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);
}

Podsumowanie

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