數(shù)據(jù)結(jié)構(gòu)算法:寫了一個(gè)八皇后解法

先用最笨的窮舉法求解，有空再研究更好的解法：
    # -*- coding: gb2312 -*-
    size = 8 # 棋盤大小
    EMPTY = "O" # 空位
    QUEEN = "X" # 皇后
    # 查看棋盤的信息
    def show_board(cols):
    for i in range(1, size + 1):
    for j in range(1, size + 1):
    if j == cols[i]:
    print QUEEN,
    else:
    print EMPTY,
    print "\n",
    # 檢測棋盤上皇后擺法是否合法
    # return:
    # True(不沖突), False(有沖突)
    def check_board(cols):
    for i in range(1, size):
    for j in range(i + 1, size + 1):
    if (j - i) == abs(cols[j] - cols[i]):
    return False
    return True
    solve_count = 0
    for a in range(1, size + 1):
    for b in range(1, size + 1):
    for c in range(1, size + 1):
    for d in range(1, size + 1):
    for e in range(1, size + 1):
    for f in range(1, size + 1):
    for g in range(1, size + 1):
    for h in range(1, size + 1):
    if a <> b and a <> c and a <> d and a <> e and a <> f and a <> g and a <> h and b <> c and b <> d and b <> e and b <> f and b <> g and b <> h and c <> d and c <> e and c <> f and c <> g and c <> h and d <> e and d <> f and d <> g and d <> h and e <> f and e <> g and e <> h and f <> g and f <> h and g <> h:
    cols = [0,a,b,c,d,e,f,g,h]
    if check_board(cols):
    solve_count += 1
    show_board(cols)
    print "\n",
    print "found %i solves." % solve_count
    posted on 2006-01-08 16:40 木野狐(Neil Chen) 閱讀(541) 評(píng)論(1) 編輯 收藏 所屬分類: 編程思考 、Python
    Feedback
    #1樓 [樓主] 2006-01-13 00:43 木野狐
    參考 All Start From A Game 改進(jìn)了程序，速度提高了很多，并且能計(jì)算 n 皇后問題了：
    # -*- coding: gb2312 -*-
    size = 8 # 棋盤大小
    EMPTY = "O" # 空位
    QUEEN = "X" # 皇后
    # 查看棋盤的信息
    def show_board(cols):
    for i in range(size):
    for j in range(size):
    if j == int(cols[i]) - 1:
    print QUEEN,
    else:
    print EMPTY,
    print "\n",
    # 檢測棋盤上皇后擺法是否合法
    # return:
    # True(不沖突), False(有沖突)
    def check_board(cols):
    for i in range(size - 1):
    for j in range(i + 1, size):
    if j - i == abs(int(cols[j]) - int(cols[i])):
    return False
    return True
    # 得到全排列
    def permute(seq):
    seqn = [ seq.pop() ]
    while seq:
    newseq = []
    new = seq.pop()
    #print "seq:",seq,’seqn’, seqn ,’new’, new
    for i in range(len(seqn)):
    item = seqn[i]
    for j in range(len(item)+1):
    newseq.append(’’.join([item[:j],new,item[j:]]))
    seqn = newseq
    #print ’newseq’,newseq
    return seqn
    if __name__ == "__main__":
    solve_count = 0
    numbers = ’’.join([str(i) for i in range(1, size + 1)])
    for x in permute(list(numbers)):
    y = list(x)
    if check_board(y):
    solve_count += 1
    show_board(y)
    print "\n",
    print "found %i solves." % solve_count