-
Notifications
You must be signed in to change notification settings - Fork 1
/
eight-queues.php
88 lines (75 loc) · 1.89 KB
/
eight-queues.php
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
<?php
class Solution {
protected $result = [];
protected $n = 0;
protected $finish = 0;
/**
* @param Integer $n
* @return String[][]
*/
function solveNQueens($n)
{
$this->n = $n;
$this->calculate(0);
return $this->makeResult();
}
protected function calculate($row)
{
if ($row === $this->n) {
$this->finish = 1;
return ;
}
for ($column = 0; $column < $this->n; $column++) {
if ($this->isOk($row, $column)) {
$this->result[$row] = $column;
$this->calculate($row+1);
if ($this->finish) {
return ;
}
}
}
}
protected function isOk($row, $column)
{
$leftUp = $column - 1;
$rightUp = $column + 1;
for ($i = $row - 1; $i >= 0; $i--) {
// 当前列
if ($this->result[$i] === $column) {
return false;
}
// 左上角
if ($leftUp >=0 && $this->result[$i] === $leftUp) {
return false;
}
// 右上角
if ($rightUp < $this->n && $this->result[$i] === $rightUp) {
return false;
}
$leftUp--;
$rightUp++;
}
return true;
}
protected function makeResult()
{
$ret = [];
for ($row = 0; $row < $this->n; $row++) {
$str = '';
for ($column = 0; $column < $this->n; $column++) {
if ($this->result[$row] === $column) {
$str .= 'Q ';
} else {
$str .= '. ';
}
}
$ret[] = $str;
}
return $ret;
}
}
$n = 8;
$ret = (new Solution())->solveNQueens($n);
foreach ($ret as $value) {
echo $value.PHP_EOL;
}