递归学习:N皇后 [暨接受六神指点后感]

来源:转载

def calcQueens(size): board=[-1]*size return queens(board,0,size)def queens(board,current,size): if(current==size): for i in board: print i return True else: for i in range(size): board[current]=i if(noConflicts(board,current)): done=queens(board,current+1,size) if(done): return True return Falsedef noConflicts(board,current): for i in range(current): if(board[i]==board[current]): return False if(current-i==abs(board[current]-board[i])): return False return True

只比最简单那种递归多拐了一个弯,就让我苦思冥想了好几个小时,最终还是靠高人指点才终于理清楚……

            for i in range(size):
                  board[current]=i
                  if(noConflicts(board,current)):
                     done=queens(board,current+1,size)

这一块是重点,它把递归嵌在一个循环里,这样就要理解成 把一个大问题拆分成多个(至多为size个)子问题。

为了更好的理解递归,要去注意函数的整体意义,把每一个子函数看成一个黑盒,理解整体功能,再打开黑盒来看清每两层黑盒之间如何联系。

这个函数的整体意义是:对于一个大小为size * size的board,假设board里的前current行都已经放好了皇后的前提下,是否存在一个合法的N皇后解。

里面装了多个小黑盒,直到找到current+1位上的皇后位置合适了那个黑盒才停,而判断位置是否合适,就又要用再里面一层的小黑盒。

每个current对应一列 整个找到解的过程就是用循环填满行,递归填满列。

在6666666神的帮助下,我对递归有了更多的理解,要先看整体,然后分析每层是怎么传递的。

对所有无所求地给小白们提供耐心帮助的大神们表示由衷的敬意。



分享给朋友:
您可能感兴趣的文章:
随机阅读: