八皇后问题

php解八皇后

回忆 八皇后问题,我心底放了多年的痛。还记得08年在西电上补习班,大神讲师三五句话就说完了八皇后问题,黑板上涂涂画画就讲完了算法原理。然而我,坐在下面一脸懵逼,很尴尬。被嘲讽是必然的。。。。 恰好昨天写动态规划,又想起了这个问题。干脆来实现下 直接上naive方法 逐行扫描,对于第i (0 <= i <= N-1)行,根据历史路径$histories(是一个(x,y)坐标集合,0 < = x <i, 0 <= y <= N-1)来生成当前行可用列$availables。 history中已经使用过的列y,不能再用 history中的(x,y)点,和当前(i,j), 0 <= i < = N-1,存在这样的关系:dist=i-x, (i,j) = (x+dist,y+dist), 或者(i,j) = (x-dist,y+dist),则说明当前j列位置不可用,因为他和之前的点在同一斜线上。 <?php const N = 12; $count = 0; function printHistory($row, $histories){ echo "==========n==========\n"; foreach($histories as $history){ echo "($histo...
执行时间: 32.577991485596 毫秒