图 10-1 4皇后问题的初始搜索树
对每种情况再进行扩展,在第二行摆上不会互相攻击的另一个皇后,如图10-2所示.
图 10-2 放置了第二个皇后的4皇后搜索树
第一个和最后一个中间解不能再放下第三个皇后了.中间的四个可以放置第三个,而最中间的两个则可以放置第四个皇后(如图10-3所示).
图 10-3 4皇后问题的最终解
如此详尽地阐述搜索树让我们看到,4皇后有2个解.通过计算来解19皇后就难得多了.在第19层搜索树上,有4 968 057 848个节点,而整个树的节点更多,需要很长很长时间才能算出结果.
Donald Knuth(1975)提出了另一种全新的方法来估算搜索树的形状和大小.它的方法会随机地向下遍历