国际象棋棋盘由8*8的格子组成,皇后是最厉害的一种棋子可以吃掉横线,斜线,直线上的任意一个子.现在给你5个皇后,放在棋盘上.

保证:
1.这5个棋子彼此不会攻击.
2.再放任何一个棋子在这个棋盘上都会被这5个棋子中的某个棋子吃掉!

要求得到所以可能的排列方式。

大家讨论一下有什么算法可以解决这个问题。

以下是我的程序：

Copy code

lineUsed=[-1,-1,-1,-1,-1,-1,-1,-1]#lineUsed[i]=-1 means line i is empty,lineUsed[i]=j means line i is used by a Queen who is right in row j
rowUsed=[-1,-1,-1,-1,-1,-1,-1,-1] #rowUsed[i]=-1 means row i is empty,rowUsed[i]=j means row i is used by a Queen who is right in line j
boxUsed=[]
diagonal_1_used=[]
diagonal_2_used=[]

def Test(boxList):
   lineUsed2=[-1,-1,-1,-1,-1,-1,-1,-1]
   rowUsed2=[-1,-1,-1,-1,-1,-1,-1,-1]
   diagonal_1_used2=[]
   diagonal_2_used2=[]
   for m in range(0,len(boxList)):
       lineUsed2[boxList[m]//8]=boxList[m]%8
       rowUsed2[boxList[m]%8]=boxList[m]//8
       diagonal_1_used2.append((boxList[m]%8)+(boxList[m]//8))
       diagonal_2_used2.append((boxList[m]//8)-(boxList[m]%8))
   for n in range(0,64):
       if lineUsed2[n//8]==-1 and rowUsed2[n%8]==-1 and (not (n//8)+(n%8) in diagonal_1_used2) and (not (n//8)-(n%8) in diagonal_2_used2):
           return False
   return True
   
def myPrint(boxList):
   for i in range(0,len(boxList)):
       L_N=boxList[i]//8
       R_N=boxList[i]%8
       print L_N,'-',R_N,'     ',
   print ''

count=0

def Try(boxNum):
   global count
   if boxNum<64:
       for set in [True,False]:
           lineNum=boxNum//8
           rowNum=boxNum%8
           if (lineUsed[lineNum]==-1) and (rowUsed[rowNum]==-1) and (not lineNum+rowNum in diagonal_1_used) and (not lineNum-rowNum in diagonal_2_used) and (not boxNum in boxUsed) and set:
               boxUsed.append(boxNum)
               lineUsed[lineNum]=rowNum
               rowUsed[rowNum]=lineNum
               diagonal_1_used.append(lineNum+rowNum)
               diagonal_2_used.append(lineNum-rowNum)
               if len(boxUsed)<5:
                   Try(boxNum+8-rowNum)
               if len(boxUsed)==5:
                   if Test(boxUsed):
                       count+=1
                       print count,'         '
                       myPrint(boxUsed)
               boxUsed.pop()
               lineUsed[lineNum]=-1
               rowUsed[rowNum]=-1
               diagonal_1_used.pop()
               diagonal_2_used.pop()
           if set==False:
               Try(boxNum+1)

Try(0)
input()

Quote:

引用第2楼fengtao57于2007-01-09 14:32发表的:
程序不是重要的
主要是算法
你直接写算法流程就行了嘛

基本思想是：
先排列出一个五皇后互相不打架的局面（当然要把所有可能都排出来），再逐个格子判断是否能放下第六个皇后，如果所有格子都无法放下第六个皇后，则输出一个结果，并统计总方案数。