1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
class sudoxu |
4
|
|
|
{ |
5
|
|
|
|
6
|
|
|
public $sudoku, |
7
|
|
|
$result, |
8
|
|
|
$number; |
9
|
|
|
private $limit, |
10
|
|
|
$sq, |
11
|
|
|
$chars, |
12
|
|
|
$stack = array('1','2','3','4','5','6','7','8','9','0','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'); |
13
|
|
|
|
14
|
|
|
public function __construct($limit = 9) |
15
|
|
|
{ |
16
|
|
|
ini_set('memory_limit', -1); |
17
|
|
|
set_time_limit(0); |
18
|
|
|
|
19
|
|
|
ini_set('display_errors',1); |
20
|
|
|
error_reporting(E_ALL); |
21
|
|
|
|
22
|
|
|
$this->number = 0; |
23
|
|
|
$this->limit = $limit; |
24
|
|
|
$this->sq = (int)sqrt($this->limit); |
25
|
|
|
|
26
|
|
|
$this->logic(); |
27
|
|
|
|
28
|
|
|
return $this; |
29
|
|
|
|
30
|
|
|
} |
31
|
|
|
|
32
|
|
|
public function logic() |
33
|
|
|
{ |
34
|
|
|
if(count($this->stack) < $this->limit) |
35
|
|
|
{ |
36
|
|
|
echo 'error'; |
37
|
|
|
exit; |
38
|
|
|
} |
39
|
|
|
} |
40
|
|
|
|
41
|
|
|
public function set($number) |
42
|
|
|
{ |
43
|
|
|
$this->limit = $number; |
44
|
|
|
$this->sq = (int)sqrt($this->limit); |
45
|
|
|
|
46
|
|
|
return $this; |
47
|
|
|
|
48
|
|
|
} |
49
|
|
|
|
50
|
|
|
private function return_row($cell) |
51
|
|
|
{ |
52
|
|
|
return floor($cell / $this->limit); |
53
|
|
|
|
54
|
|
|
} |
55
|
|
|
|
56
|
|
|
private function return_col($cell) |
57
|
|
|
{ |
58
|
|
|
return $cell % $this->limit; |
59
|
|
|
|
60
|
|
|
} |
61
|
|
|
|
62
|
|
|
private function return_block($cell) |
63
|
|
|
{ |
64
|
|
|
return floor($this->return_row($cell) / $this->sq) * $this->sq + floor($this->return_col($cell) / $this->sq); |
65
|
|
|
|
66
|
|
|
} |
67
|
|
|
|
68
|
|
View Code Duplication |
private function is_possible_row($number, $row) |
|
|
|
|
69
|
|
|
{ |
70
|
|
|
$possible = true; |
71
|
|
|
for ($x = 0; $x < $this->limit; $x++) |
72
|
|
|
{ |
73
|
|
|
if (isset($this->sudoku[$row * $this->limit + $x]) && $this->sudoku[$row * $this->limit + $x] == $number) |
74
|
|
|
{ |
75
|
|
|
$possible = false; |
76
|
|
|
} |
77
|
|
|
} |
78
|
|
|
|
79
|
|
|
return $possible; |
80
|
|
|
} |
81
|
|
|
|
82
|
|
View Code Duplication |
private function is_possible_col($number, $col) |
|
|
|
|
83
|
|
|
{ |
84
|
|
|
$possible = true; |
85
|
|
|
for ($x = 0; $x < $this->limit; $x++) |
86
|
|
|
{ |
87
|
|
|
if (isset($this->sudoku[$col + $this->limit * $x]) && $this->sudoku[$col + $this->limit * $x] == $number) |
88
|
|
|
{ |
89
|
|
|
$possible = false; |
90
|
|
|
} |
91
|
|
|
} |
92
|
|
|
|
93
|
|
|
return $possible; |
94
|
|
|
} |
95
|
|
|
|
96
|
|
|
private function is_possible_block($number, $block) |
97
|
|
|
{ |
98
|
|
|
$possible = true; |
99
|
|
|
for ($x = 0; $x < $this->limit; $x++) |
100
|
|
|
{ |
101
|
|
|
$index = floor($block / $this->sq) * $this->sq * $this->limit + $x % $this->sq + $this->limit * floor($x / $this->sq) + $this->sq * ($block % $this->sq); |
102
|
|
|
if (isset($this->sudoku[$index]) && $this->sudoku[$index] == $number) |
103
|
|
|
{ |
104
|
|
|
$possible = false; |
105
|
|
|
} |
106
|
|
|
} |
107
|
|
|
|
108
|
|
|
return $possible; |
109
|
|
|
} |
110
|
|
|
|
111
|
|
|
private function is_possible_number($cell, $number) |
112
|
|
|
{ |
113
|
|
|
$row = $this->return_row($cell); |
114
|
|
|
$col = $this->return_col($cell); |
115
|
|
|
$block = $this->return_block($cell); |
116
|
|
|
|
117
|
|
|
return ($this->is_possible_row($number, $row) && $this->is_possible_col($number, $col) && $this->is_possible_block($number, $block)); |
118
|
|
|
} |
119
|
|
|
|
120
|
|
|
private function is_correct_row($row) |
121
|
|
|
{ |
122
|
|
|
$row_temp = array(); |
123
|
|
|
for ($x = 0; $x < $this->limit; $x++) |
124
|
|
|
{ |
125
|
|
|
if(!isset($this->sudoku[$row * $this->limit + $x])) |
126
|
|
|
{ |
127
|
|
|
$this->sudoku[$row * $this->limit + $x] = null; |
128
|
|
|
} |
129
|
|
|
$row_temp[$x] = $this->sudoku[$row * $this->limit + $x]; |
130
|
|
|
} |
131
|
|
|
|
132
|
|
|
return count(array_diff($this->chars, $row_temp)) == 0; |
133
|
|
|
} |
134
|
|
|
|
135
|
|
|
private function is_correct_col($col) |
136
|
|
|
{ |
137
|
|
|
$col_temp = array(); |
138
|
|
|
for ($x = 0; $x < $this->limit; $x++) |
139
|
|
|
{ |
140
|
|
|
$col_temp[$x] = $this->sudoku[$col + $x * $this->limit]; |
141
|
|
|
} |
142
|
|
|
return count(array_diff($this->chars, $col_temp)) == 0; |
143
|
|
|
} |
144
|
|
|
|
145
|
|
|
private function is_correct_block($block) |
146
|
|
|
{ |
147
|
|
|
$block_temp = array(); |
148
|
|
|
for ($x = 0; $x < $this->limit; $x++) |
149
|
|
|
{ |
150
|
|
|
$lookingfor = floor($block / $this->sq) * ($this->sq * $this->limit) + ($x % $this->sq) + $this->limit * floor($x / $this->sq) + $this->sq * ($block % $this->sq); |
151
|
|
|
|
152
|
|
|
if (!isset($this->sudoku[$lookingfor])) |
153
|
|
|
{ |
154
|
|
|
$this->sudoku[$lookingfor] = null; |
155
|
|
|
} |
156
|
|
|
|
157
|
|
|
$block_temp[$x] = $this->sudoku[$lookingfor]; |
158
|
|
|
} |
159
|
|
|
return count(array_diff($this->chars, $block_temp)) == 0; |
160
|
|
|
} |
161
|
|
|
|
162
|
|
|
private function is_solved_sudoku() |
163
|
|
|
{ |
164
|
|
|
for ($x = 0; $x < $this->limit; $x++) |
165
|
|
|
{ |
166
|
|
|
if (!$this->is_correct_block($x) or !$this->is_correct_row($x) or !$this->is_correct_col($x)) |
167
|
|
|
{ |
168
|
|
|
return false; |
169
|
|
|
break; |
|
|
|
|
170
|
|
|
} |
171
|
|
|
} |
172
|
|
|
return true; |
173
|
|
|
} |
174
|
|
|
|
175
|
|
|
private function determine_possible_values($cell) |
176
|
|
|
{ |
177
|
|
|
$possible = array(); |
178
|
|
|
for ($x = 0; $x < $this->limit; $x++) |
179
|
|
|
{ |
180
|
|
|
if ($this->is_possible_number($cell, $this->chars[$x])) |
181
|
|
|
{ |
182
|
|
|
array_unshift($possible, $this->chars[$x]); |
183
|
|
|
} |
184
|
|
|
} |
185
|
|
|
|
186
|
|
|
return $possible; |
187
|
|
|
} |
188
|
|
|
|
189
|
|
|
private function determine_random_possible_value($possible, $cell) |
190
|
|
|
{ |
191
|
|
|
return $possible[$cell][rand(0, count($possible[$cell]) - 1)]; |
192
|
|
|
} |
193
|
|
|
|
194
|
|
|
private function scan_sudoku_for_unique() |
195
|
|
|
{ |
196
|
|
|
$possible = false; |
197
|
|
|
for ($x = 0; $x < $this->limit * $this->limit; $x++) |
198
|
|
|
{ |
199
|
|
|
if (!isset($this->sudoku[$x])) |
200
|
|
|
{ |
201
|
|
|
$possible[$x] = $this->determine_possible_values($x, $this->sudoku); |
|
|
|
|
202
|
|
|
if (count($possible[$x]) == 0) |
203
|
|
|
{ |
204
|
|
|
return (false); |
205
|
|
|
break; |
|
|
|
|
206
|
|
|
} |
207
|
|
|
} |
208
|
|
|
} |
209
|
|
|
|
210
|
|
|
return $possible; |
211
|
|
|
} |
212
|
|
|
|
213
|
|
|
private function remove_attempt($attempt_array, $number) |
214
|
|
|
{ |
215
|
|
|
$new_array = array(); |
216
|
|
|
for ($x = 0; $x < count($attempt_array); $x++) |
|
|
|
|
217
|
|
|
{ |
218
|
|
|
if ($attempt_array[$x] != $number) |
219
|
|
|
{ |
220
|
|
|
array_unshift($new_array, $attempt_array[$x]); |
221
|
|
|
} |
222
|
|
|
} |
223
|
|
|
return $new_array; |
224
|
|
|
} |
225
|
|
|
|
226
|
|
|
|
227
|
|
|
private function next_random($possible) |
228
|
|
|
{ |
229
|
|
|
$max = $this->limit; |
230
|
|
|
for ($x = 0; $x < $this->limit * $this->limit; $x++) |
231
|
|
|
{ |
232
|
|
|
if (!isset($possible[$x])) |
233
|
|
|
{ |
234
|
|
|
$possible[$x] = null; |
235
|
|
|
} |
236
|
|
|
|
237
|
|
|
if ((count($possible[$x]) <= $max) && (count($possible[$x]) > 0)) |
238
|
|
|
{ |
239
|
|
|
$max = count($possible[$x]); |
240
|
|
|
$min_choices = $x; |
241
|
|
|
} |
242
|
|
|
} |
243
|
|
|
return $min_choices; |
|
|
|
|
244
|
|
|
} |
245
|
|
|
|
246
|
|
|
|
247
|
|
|
private function build() |
248
|
|
|
{ |
249
|
|
|
$this->sudoku = array(); |
250
|
|
|
$this->chars = array(); |
251
|
|
|
|
252
|
|
|
for ($i = 0; $i < $this->limit; $i++) |
253
|
|
|
{ |
254
|
|
|
$this->chars[] = $this->stack[$i]; |
255
|
|
|
} |
256
|
|
|
} |
257
|
|
|
|
258
|
|
|
public function microtime() |
259
|
|
|
{ |
260
|
|
|
return microtime(true); |
261
|
|
|
} |
262
|
|
|
|
263
|
|
|
public function generate() |
264
|
|
|
{ |
265
|
|
|
$start = $this->microtime(); |
266
|
|
|
$this->build(); |
267
|
|
|
|
268
|
|
|
$x = 0; |
269
|
|
|
$saved = array(); |
270
|
|
|
$saved_sud = array(); |
271
|
|
|
while (!$this->is_solved_sudoku()) |
272
|
|
|
{ |
273
|
|
|
$x++; |
274
|
|
|
$next_move = $this->scan_sudoku_for_unique(); |
275
|
|
|
|
276
|
|
|
if ($next_move == false) |
|
|
|
|
277
|
|
|
{ |
278
|
|
|
$next_move = array_pop($saved); |
279
|
|
|
$this->sudoku = array_pop($saved_sud); |
280
|
|
|
} |
281
|
|
|
|
282
|
|
|
$what_to_try = $this->next_random($next_move); |
283
|
|
|
$attempt = $this->determine_random_possible_value($next_move, $what_to_try); |
284
|
|
|
|
285
|
|
|
|
286
|
|
|
if (count($next_move[$what_to_try]) > 1) |
287
|
|
|
{ |
288
|
|
|
$next_move[$what_to_try] = $this->remove_attempt($next_move[$what_to_try], $attempt); |
289
|
|
|
array_push($saved, $next_move); |
290
|
|
|
array_push($saved_sud, $this->sudoku); |
291
|
|
|
} |
292
|
|
|
$this->sudoku[$what_to_try] = $attempt; |
293
|
|
|
} |
294
|
|
|
|
295
|
|
|
$timing = $this->microtime() - $start; |
296
|
|
|
$this->result = array( |
297
|
|
|
'created_in' => round($timing,2), |
298
|
|
|
'difficulty' => 'N/A' |
299
|
|
|
); |
300
|
|
|
|
301
|
|
|
return $this; |
302
|
|
|
} |
303
|
|
|
|
304
|
|
|
private function array2export() |
305
|
|
|
{ |
306
|
|
|
return array( |
307
|
|
|
'sudoku' => $this->sudoku, |
308
|
|
|
'limit' => $this->limit, |
309
|
|
|
'result' => $this->result, |
310
|
|
|
|
311
|
|
|
); |
312
|
|
|
} |
313
|
|
|
|
314
|
|
|
public function to($to) |
315
|
|
|
{ |
316
|
|
|
if($to == 'json') |
317
|
|
|
{ |
318
|
|
|
return json_encode($this->array2export()); |
319
|
|
|
} |
320
|
|
|
else if($to == 'serialize') |
321
|
|
|
{ |
322
|
|
|
return serialize($this->array2export()); |
323
|
|
|
} |
324
|
|
|
else if($to == 'html') |
325
|
|
|
{ |
326
|
|
|
return serialize($this->array2export()); |
327
|
|
|
} |
328
|
|
|
} |
329
|
|
|
|
330
|
|
|
|
331
|
|
|
public function draw($echo = true) |
332
|
|
|
{ |
333
|
|
|
|
334
|
|
|
|
335
|
|
|
$string = "<table cellpadding='0' cellspacing='0' style='margin:0 auto;font:30px Arial;border:3px solid black'>"; |
336
|
|
|
|
337
|
|
|
for ($u = 0; $u < $this->limit; $u++) |
338
|
|
|
{ |
339
|
|
|
|
340
|
|
|
|
341
|
|
|
if (($u + 1) % $this->sq == '0') |
342
|
|
|
{ |
343
|
|
|
$border = 3; |
344
|
|
|
} else { |
345
|
|
|
$border = 1; |
346
|
|
|
} |
347
|
|
|
|
348
|
|
|
$string .= '<tr>'; |
349
|
|
|
|
350
|
|
|
for ($v = 0; $v < $this->limit; $v++) |
351
|
|
|
{ |
352
|
|
|
|
353
|
|
|
|
354
|
|
|
if (($v + 1) % $this->sq == '0') |
355
|
|
|
{ |
356
|
|
|
$border2 = 3; |
357
|
|
|
} else { |
358
|
|
|
$border2 = 1; |
359
|
|
|
} |
360
|
|
|
|
361
|
|
|
$string .= '<td |
362
|
|
|
data-row="'.$u.'" |
363
|
|
|
data-col="'.$v.'" |
364
|
|
|
style="border: 1px solid black;border-bottom:' . $border . 'px solid black;border-right:' . $border2 . 'px solid black;line-height: 50px; width: 50px; text-align: center; vertical-align: middle;">'; |
365
|
|
|
$string .=($this->sudoku[$v * $this->limit + $u]); |
366
|
|
|
$string .= '</td>'; |
367
|
|
|
|
368
|
|
|
} |
369
|
|
|
|
370
|
|
|
$string .= '</tr>'; |
371
|
|
|
|
372
|
|
|
} |
373
|
|
|
|
374
|
|
|
$string .= "</table>"; |
375
|
|
|
|
376
|
|
|
|
377
|
|
|
if($echo === true) |
378
|
|
|
{ |
379
|
|
|
echo $string; |
380
|
|
|
} |
381
|
|
|
else |
382
|
|
|
{ |
383
|
|
|
return $string; |
384
|
|
|
} |
385
|
|
|
|
386
|
|
|
} |
387
|
|
|
|
388
|
|
|
} |
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.