php 实现八皇后问题

浏览数：49 / 时间：2015年06月09日

php实现的八皇后问题，可以推广到N皇后

<?php 
class Empress{
	private $queen;//存储位置，例如$queen[2] = 3表示第三行的第四列位置，行列从0计数
	public static $count;//总共有多少种排列顺序
 	
	private $m;//规模数量
	
	//设置几皇后，返回排列结果
	public function getResult($m){
		$this->m = $m;
		$this->put(0);
	}
	
	
	//判断第$n行放置位置$queen[$n] = $i 是否和前面的行冲突(同行，同列冲突，对角线冲突)
	/**
	 * @param $n 第n行
	 * @return  bool是否冲突
	 */
	private function attack($n){
		for ($i=0;$i<$n;$i++){
			if($this->queen[$n] == $this->queen[$i] ||abs($this->queen[$n]-$this->queen[$i]) == abs($n-$i)){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 
	 * 打印函数
	 */
	private function show(){
		for ($i=0;$i<$this->m;$i++){
			echo $this->queen[$i].‘--‘;
		}
	}
	
	/**
	 * 
	 * 放置第n行的位置
	 */
	private function put($n){
		for ($i=0;$i<$this->m;$i++){
			$this->queen[$n] = $i;//依次试探
			$tmp_res = $this->attack($n);
			//如果没有冲突，要么继续放置下一行，要么到最后一行了。
			if(!$tmp_res){
				if($n==$this->m-1){
					$this->show();
					echo ‘第‘.(self::$count+1).‘种排列方法‘;
					echo "<br/>";
					self::$count++;
				}else{
					$this->put($n+1);
				}
			}
		}
	}
}

class Client{
	public static function main(){
		$obj = new Empress();
		$obj->getResult(4);
	}
}
Client::main();

?>

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

php 实现八皇后问题