回溯之N皇后
2019-12-13 本文已影响0人
猿来是八阿哥
N皇后问题：在 n x n 的棋盘上放置 N 个皇后，使其不能相互攻击。
1. 问题分析
- 皇后相互攻击是指：在皇后 Q1 的
水平垂直正对角线反对角线上，都不能有其他皇后。 - 假设：皇后 Q1 的位置在 P1=(x1, y1)、皇后 Q2 的位置在 P2=(x2, y2)，两个皇后相互攻击的问题可以转化为：
P1 和 P2 所代表的直线，其斜率不能为：0=水平线、-1=正对角线、1=反对角线、无穷大=垂直线 - 即：
k = (y1 == y2) ? NUMBER_MAX : (x1 - x2) / (y1 - y2)，如果k in (0, 1, -1, NUMBER_MAX)，Q1 和 Q2 能相互攻击，否则 Q1 和 Q2 不能相互攻击。
2. 下面给出 php 版的实现
<?php
class Solution{
private $_showDetail = false;
private $_detailSteps = [];
public function __construct($showDetail=false){
$this->_showDetail = boolval($showDetail);
}
public function nqueen($n){
$queenPositions = [];
$res = $this->_backtraceFindNQueenPosition(1, $n, $queenPositions);
return [$res, $queenPositions, $this->_detailSteps];
}
private function _backtraceFindNQueenPosition($row, $totalRows, &$position){
if($row > $totalRows){
return true;
}
for($col=1; $col<=$totalRows; $col++){
if($this->_showDetail){
$tempPosition = $position;
$tempPosition[$row] = $col;
array_push($this->_detailSteps, $tempPosition);
}
if($this->_areTheseQueenSafe($position, $row, $col)){
$position[$row] = $col;
if($this->_backtraceFindNQueenPosition($row+1, $totalRows, $position)){
return true;
}
unset($position[$row]);
}
}
}
/**
* @param $positions
* @return bool
*/
private function _areTheseQueenSafe($positions, $row, $col){
if(0 == count($positions)){
return true;
}
foreach ($positions as $prow => $pcol) {
$lineK = $row == $prow ? PHP_INT_MAX : ($col - $pcol) / ($row - $prow);
if(
$lineK == 0 || // same row
$lineK == PHP_INT_MAX || // same col
$lineK == 1 || // on line: left-top to right-bottom (0, 0) is at left-top
$lineK == -1 // on line: right-top to left-bottom (0, 0) is at left-top
){
return false;
}
}
return true;
}
public function printNQueenResult($result, $n){
list($successed, $position, $steps) = $result;
if($successed){
echo 'A solution for '.$n.'-queens is: '.PHP_EOL;
foreach ($position as $col) {
echo str_repeat(' x ', $col-1);
echo ' Q ';
echo str_repeat(' x ', $n-$col);
echo PHP_EOL;
}
if(0 != count($steps)){
echo PHP_EOL;
foreach ($steps as $k => $pos) {
echo 'This solution step-'.strval($k+1).' is:'.PHP_EOL;
foreach ($pos as $col) {
echo str_repeat(' x ', $col-1);
echo ' Q ';
echo str_repeat(' x ', $n-$col);
echo PHP_EOL;
}
}
}
}else{
echo 'No solution found for '.$n.'-queens...'.PHP_EOL;
}
}
}
$n = 4;
//$s = new Solution();
$s = new Solution(true);
$res = $s->nqueen($n);
$s->printNQueenResult($res, $n);
echo PHP_EOL;
3. 下面是整个回溯的过程
A solution for 4-queens is:
x Q x x
x x x Q
Q x x x
x x Q x
This solution step-1 is:
Q x x x
This solution step-2 is:
Q x x x
Q x x x
This solution step-3 is:
Q x x x
x Q x x
This solution step-4 is:
Q x x x
x x Q x
This solution step-5 is:
Q x x x
x x Q x
Q x x x
This solution step-6 is:
Q x x x
x x Q x
x Q x x
This solution step-7 is:
Q x x x
x x Q x
x x Q x
This solution step-8 is:
Q x x x
x x Q x
x x x Q
This solution step-9 is:
Q x x x
x x x Q
This solution step-10 is:
Q x x x
x x x Q
Q x x x
This solution step-11 is:
Q x x x
x x x Q
x Q x x
This solution step-12 is:
Q x x x
x x x Q
x Q x x
Q x x x
This solution step-13 is:
Q x x x
x x x Q
x Q x x
x Q x x
This solution step-14 is:
Q x x x
x x x Q
x Q x x
x x Q x
This solution step-15 is:
Q x x x
x x x Q
x Q x x
x x x Q
This solution step-16 is:
Q x x x
x x x Q
x x Q x
This solution step-17 is:
Q x x x
x x x Q
x x x Q
This solution step-18 is:
x Q x x
This solution step-19 is:
x Q x x
Q x x x
This solution step-20 is:
x Q x x
x Q x x
This solution step-21 is:
x Q x x
x x Q x
This solution step-22 is:
x Q x x
x x x Q
This solution step-23 is:
x Q x x
x x x Q
Q x x x
This solution step-24 is:
x Q x x
x x x Q
Q x x x
Q x x x
This solution step-25 is:
x Q x x
x x x Q
Q x x x
x Q x x
This solution step-26 is:
x Q x x
x x x Q
Q x x x
x x Q x
4. 算法要点
- 回溯的实现是：
递归+循环+回退，即：在step-n时，循环选择每一种可能，当step-[n+x]证明step-n时的选择不正确时，回到step-n，选择另一种可能。
