|
1
|
|
|
<?php |
|
2
|
|
|
|
|
3
|
|
|
namespace Chipulaja\Algo\Backtrack\Sudoku; |
|
4
|
|
|
|
|
5
|
|
|
class SudokuSolverCara1 |
|
6
|
|
|
{ |
|
7
|
|
|
private $soal = []; |
|
8
|
|
|
private $jawaban = []; |
|
9
|
|
|
private $emptyLocation = []; |
|
10
|
|
|
|
|
11
|
1 |
|
public function tryToSolve( |
|
12
|
|
|
$data, |
|
13
|
|
|
$emptyLocation = [], |
|
14
|
|
|
$possibilitiesValue = [], |
|
15
|
|
|
$prevValue = null, |
|
16
|
|
|
$lastPosition = null, |
|
17
|
|
|
$tempSolusion = [] |
|
18
|
|
|
) { |
|
19
|
1 |
|
if (empty($emptyLocation)) { |
|
20
|
1 |
|
$emptyLocation = $this->getEmptyLocation($data); |
|
21
|
1 |
|
$this->soal = $data; |
|
22
|
1 |
|
$this->emptyLocation = $emptyLocation; |
|
23
|
1 |
|
foreach ($emptyLocation as $position => $location) { |
|
24
|
1 |
|
$possibilitiesValue[$position] = $this->getPossibilitiesValue( |
|
25
|
1 |
|
$location, |
|
26
|
1 |
|
$data |
|
27
|
|
|
); |
|
28
|
|
|
} |
|
29
|
|
|
} |
|
30
|
|
|
|
|
31
|
1 |
|
$newData = $data; |
|
32
|
1 |
|
if ($lastPosition === null) { |
|
33
|
1 |
|
$keysLocation = array_keys($emptyLocation); |
|
34
|
1 |
|
$lastPosition = (int)$keysLocation[0]; |
|
35
|
|
|
} |
|
36
|
|
|
|
|
37
|
1 |
|
$record = false; |
|
38
|
1 |
|
foreach ($emptyLocation as $position => $location) { |
|
39
|
1 |
|
if (sizeof($tempSolusion) >= sizeof($emptyLocation)) { |
|
40
|
1 |
|
$this->jawaban = $tempSolusion; |
|
41
|
1 |
|
break; |
|
42
|
|
|
} |
|
43
|
|
|
|
|
44
|
1 |
|
if ($position == $lastPosition) { |
|
45
|
1 |
|
$record = true; |
|
46
|
|
|
} |
|
47
|
|
|
|
|
48
|
1 |
|
if ($record === false) { |
|
49
|
1 |
|
continue; |
|
50
|
|
|
} |
|
51
|
1 |
|
$lastPosition = $position; |
|
52
|
1 |
|
$value = $this->getNextValue($prevValue, $possibilitiesValue[$position]); |
|
53
|
1 |
|
if ($value === null) { |
|
54
|
1 |
|
$prevLocation = $this->getPrevLocation($lastPosition, $emptyLocation); |
|
55
|
1 |
|
$position = key($prevLocation); |
|
56
|
1 |
|
$lastPosition = $position; |
|
57
|
1 |
|
$x = $prevLocation[$position]["x"]; |
|
58
|
1 |
|
$y = $prevLocation[$position]["y"]; |
|
59
|
1 |
|
$prevValue = $tempSolusion[$lastPosition]; |
|
60
|
1 |
|
$newData[$x][$y] = 0; |
|
61
|
1 |
|
array_pop($tempSolusion); |
|
62
|
|
|
|
|
63
|
1 |
|
$tempSolusion = $this->tryToSolve( |
|
64
|
1 |
|
$newData, |
|
65
|
1 |
|
$emptyLocation, |
|
66
|
1 |
|
$possibilitiesValue, |
|
67
|
1 |
|
$prevValue, |
|
68
|
1 |
|
$position, |
|
69
|
1 |
|
$tempSolusion |
|
70
|
|
|
); |
|
71
|
|
|
} else { |
|
72
|
1 |
|
$isValidValue = $this->isValidValue($location, $newData, $value); |
|
73
|
1 |
|
$x = $location["x"]; |
|
74
|
1 |
|
$y = $location["y"]; |
|
75
|
1 |
|
$newData[$x][$y] = $value; |
|
76
|
1 |
|
if ($isValidValue === true) { |
|
77
|
1 |
|
$tempSolusion[$position] = $value; |
|
78
|
1 |
|
$prevValue = null; |
|
79
|
|
|
} else { |
|
80
|
1 |
|
$newData[$x][$y] = 0; |
|
81
|
1 |
|
$tempSolusion = $this->tryToSolve( |
|
82
|
1 |
|
$newData, |
|
83
|
1 |
|
$emptyLocation, |
|
84
|
1 |
|
$possibilitiesValue, |
|
85
|
1 |
|
$value, |
|
86
|
1 |
|
$position, |
|
87
|
1 |
|
$tempSolusion |
|
88
|
|
|
); |
|
89
|
1 |
|
break; |
|
90
|
|
|
} |
|
91
|
|
|
} |
|
92
|
|
|
} |
|
93
|
|
|
|
|
94
|
1 |
|
return $tempSolusion; |
|
95
|
|
|
} |
|
96
|
|
|
|
|
97
|
1 |
View Code Duplication |
public function getEmptyLocation($data) |
|
98
|
|
|
{ |
|
99
|
1 |
|
$location = []; |
|
100
|
1 |
|
foreach ($data as $x => $cells) { |
|
101
|
1 |
|
foreach ($cells as $y => $value) { |
|
102
|
1 |
|
if (empty($value)) { |
|
103
|
1 |
|
$position = (int)($x."".$y); |
|
104
|
1 |
|
$location[$position] = [ |
|
105
|
1 |
|
'x' => $x, |
|
106
|
1 |
|
'y' => $y |
|
107
|
|
|
]; |
|
108
|
|
|
} |
|
109
|
|
|
} |
|
110
|
|
|
} |
|
111
|
|
|
|
|
112
|
1 |
|
return $location; |
|
113
|
|
|
} |
|
114
|
|
|
|
|
115
|
1 |
|
protected function getPossibilitiesValue($location, $data) |
|
116
|
|
|
{ |
|
117
|
1 |
|
$allHorisontalValue = $this->getAllHorisontalValue($location, $data); |
|
118
|
1 |
|
$allVerticalValue = $this->getAllVerticalValue($location, $data); |
|
119
|
1 |
|
$allSquereValue = $this->getAllSquereValue($location, $data); |
|
120
|
1 |
|
$allValue = array_merge( |
|
121
|
1 |
|
$allHorisontalValue, |
|
122
|
1 |
|
$allVerticalValue, |
|
123
|
1 |
|
$allSquereValue |
|
124
|
|
|
); |
|
125
|
|
|
|
|
126
|
1 |
|
$possibilitiesValue = array_diff(range(1, 9), $allValue); |
|
127
|
1 |
|
$possibilitiesValue = array_values($possibilitiesValue); |
|
128
|
1 |
|
return $possibilitiesValue; |
|
129
|
|
|
} |
|
130
|
|
|
|
|
131
|
1 |
View Code Duplication |
protected function getAllHorisontalValue($location, $data) |
|
|
|
|
|
|
132
|
|
|
{ |
|
133
|
1 |
|
$horisontalValue = []; |
|
134
|
1 |
|
$x = $location['x']; |
|
135
|
1 |
|
for ($i=$x; $i<=$x; $i++) { |
|
136
|
1 |
|
for ($j=0; $j<9; $j++) { |
|
137
|
1 |
|
if (!empty($data[$i][$j])) { |
|
138
|
1 |
|
$horisontalValue[] = $data[$i][$j]; |
|
139
|
|
|
} |
|
140
|
|
|
} |
|
141
|
|
|
} |
|
142
|
1 |
|
return $horisontalValue; |
|
143
|
|
|
} |
|
144
|
|
|
|
|
145
|
1 |
View Code Duplication |
protected function getAllVerticalValue($location, $data) |
|
|
|
|
|
|
146
|
|
|
{ |
|
147
|
1 |
|
$verticalValue = []; |
|
148
|
1 |
|
$y = $location['y']; |
|
149
|
1 |
|
for ($i=0; $i<9; $i++) { |
|
150
|
1 |
|
for ($j=$y; $j<=$y; $j++) { |
|
151
|
1 |
|
if (!empty($data[$i][$j])) { |
|
152
|
1 |
|
$verticalValue[] = $data[$i][$j]; |
|
153
|
|
|
} |
|
154
|
|
|
} |
|
155
|
|
|
} |
|
156
|
1 |
|
return $verticalValue; |
|
157
|
|
|
} |
|
158
|
|
|
|
|
159
|
1 |
|
protected function getAllSquereValue($location, $data) |
|
160
|
|
|
{ |
|
161
|
1 |
|
$squereValue = []; |
|
162
|
1 |
|
$x = $location['x']; |
|
163
|
1 |
|
$y = $location['y']; |
|
164
|
|
|
|
|
165
|
1 |
|
$iStart = 3 * floor($x/3); |
|
166
|
1 |
|
$iEnd = $iStart + 2; |
|
167
|
1 |
|
$jStart = 3 * floor($y/3); |
|
168
|
1 |
|
$jEnd = $jStart + 2; |
|
169
|
|
|
|
|
170
|
1 |
View Code Duplication |
for ($i=$iStart; $i<=$iEnd; $i++) { |
|
|
|
|
|
|
171
|
1 |
|
for ($j=$jStart; $j<=$jEnd; $j++) { |
|
172
|
1 |
|
if (!empty($data[$i][$j])) { |
|
173
|
1 |
|
$squereValue[] = $data[$i][$j]; |
|
174
|
|
|
} |
|
175
|
|
|
} |
|
176
|
|
|
} |
|
177
|
1 |
|
return $squereValue; |
|
178
|
|
|
} |
|
179
|
|
|
|
|
180
|
1 |
|
protected function isValidValue($location, $data, $value) |
|
181
|
|
|
{ |
|
182
|
1 |
|
$allHorisontalValue = $this->getAllHorisontalValue($location, $data); |
|
183
|
1 |
|
if (in_array($value, $allHorisontalValue)) { |
|
184
|
1 |
|
return false; |
|
185
|
|
|
} |
|
186
|
|
|
|
|
187
|
1 |
|
$allVerticalValue = $this->getAllVerticalValue($location, $data); |
|
188
|
1 |
|
if (in_array($value, $allVerticalValue)) { |
|
189
|
1 |
|
return false; |
|
190
|
|
|
} |
|
191
|
|
|
|
|
192
|
1 |
|
$allSquereValue = $this->getAllSquereValue($location, $data); |
|
193
|
1 |
|
if (in_array($value, $allSquereValue)) { |
|
194
|
1 |
|
return false; |
|
195
|
|
|
} |
|
196
|
|
|
|
|
197
|
1 |
|
return true; |
|
198
|
|
|
} |
|
199
|
|
|
|
|
200
|
1 |
|
protected function getPrevLocation($currentPosition, $emptyLocation) |
|
201
|
|
|
{ |
|
202
|
1 |
|
while (key($emptyLocation) !== $currentPosition) { |
|
203
|
1 |
|
next($emptyLocation); |
|
204
|
|
|
} |
|
205
|
1 |
|
$location = prev($emptyLocation); |
|
206
|
1 |
|
$position = key($emptyLocation); |
|
207
|
|
|
|
|
208
|
1 |
|
return [$position => $location]; |
|
209
|
|
|
} |
|
210
|
|
|
|
|
211
|
1 |
|
protected function getNextValue($value, $possibilitiesValue) |
|
212
|
|
|
{ |
|
213
|
1 |
|
if (!is_numeric($value)) { |
|
214
|
1 |
|
return @$possibilitiesValue[0]; |
|
215
|
|
|
} |
|
216
|
|
|
|
|
217
|
1 |
|
$key = array_search($value, $possibilitiesValue); |
|
218
|
|
|
|
|
219
|
1 |
|
return @$possibilitiesValue[$key+1]; |
|
220
|
|
|
} |
|
221
|
|
|
|
|
222
|
1 |
|
public function getAnswerBoard() |
|
223
|
|
|
{ |
|
224
|
1 |
|
$jawabanBoard = $this->soal; |
|
225
|
1 |
|
$emptyLocation = $this->emptyLocation; |
|
226
|
1 |
|
$jawaban = $this->jawaban; |
|
227
|
|
|
|
|
228
|
1 |
|
foreach ($emptyLocation as $position => $location) { |
|
229
|
1 |
|
$x = $location['x']; |
|
230
|
1 |
|
$y = $location['y']; |
|
231
|
1 |
|
$jawabanValue = $jawaban[$position]; |
|
232
|
1 |
|
$jawabanBoard[$x][$y] = $jawabanValue; |
|
233
|
|
|
} |
|
234
|
1 |
|
return $jawabanBoard; |
|
235
|
|
|
} |
|
236
|
|
|
} |
|
237
|
|
|
|
chipulaja /
algo-backtrack-sudoku
Loading history...
Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.
You can also find more detailed suggestions in the “Code” section of your repository.