欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  php教程

php解八皇后以及多皇后问题。

程序员文章站 2022-06-05 21:57:57
...

[PHP]代码

<?php
function f($q, $f = false) { /* $f 是标记,如果为 false 将重新初始化 */
	static $c = 0; /* 计数器, 解个数 */
	static $l = array(); /* 当前皇后存在的列, 键名记录行 */
	static $n = 0; /* 当前皇后,从0计数,表示第一个 */ 

	/* BUG FIX 增设初始化内容,感谢 @曹林剑 发现此BUG */
	if(!$f) {
		$c = 0;
		$l = array();
		$n=0;
	}

	/* 尝试放入皇后 */
	for($l[$n] = 0; $l[$n] < $q; $l[$n]++) {
		/* 验证皇后是否可以放入*/
		for($i = 0; $i < $n;$i++) {
			/* 验证是否可放入,冲突直接跳出本次筛选 */
			if(($l[$i] == $l[$n] || $l[$i] - $l[$n] == $i - $n || $l[$i] - $l[$n] == $n - $i )) continue 2;
		}
		/* 验证通过,可以放置本次 */

		/* 如果没有达到最后一个 */
		if($n < ($q - 1)) {
			$n++; /* 下一个皇后 */
			f($q, true); /* 第2个参数表示不会破坏内部存放数值*/
			$n--; /* 本层还有其他位置要验证, 还原后继续验证本层 */
		}
		/* 达到最后一个, 计数器+1 */
		else {
			$c++;
		}
	}
	return $c;
}

/* f(8); 可以返回 8 皇后解个数, 要想知道所有解, 可 在  "达到最后一个,计算器+1" 部分获取解详情。 */
相关标签: php