C语言名题精选百则之N后问题递归解

文章目錄

8后问题(Eight Queen Problem)是指在一个8 8的西洋棋盘上要如何放置8个皇后棋, 且不会互相吃到对方; 皇后棋可以吃掉任何它所在的那一列、那一行, 以及那两条对角线(米字型)上的任何棋子。请写一个程序, 读入一个值n表示棋盘的大小, 然后求出n n格棋盘上放n个皇后棋且不会相互吃掉对方的所有解答。

说明: 这是广义的N后问题, 因为所要求的是“所有”解答, 而不单是其中的一组, 对大多数会运用递归的人来说,这个题目反而容易做些。这一类型题目的解法通常要用到回溯(Backtrack)的技巧, 不管用递归还是不用递归都是如此, 虽然会浪费时间,但多半会找到解答。

回溯的技巧通常都以下面的面目出现, 如下所示。

S = 目前可以用得到的位置;
当S非空: 
    取出S中一个元素, 令为s
    如果s可以安全使用，那么
        定出s已经使用
        如果还可以从S再进一步，那么
            用S调用自己
        如果已经有了答案，那么
           显示答案
        把s定成没有在使用

解答见n_queen.py