'''
Created on 2012-8-16
@author: yians
'''
SIZE = 4
grid = [ [0 for col in range(SIZE)] for row in range(SIZE)]
answer = [ [0 for col in range(SIZE)] for row in range(SIZE)]
def placeCol(col):
end = True
for row in range(SIZE):
if grid[row][col] == 0:
answer[row][col] = 1
if col == SIZE - 1:
printAnswer()
answer[row][col] = 0
return
placeRelative(row, col)
placeCol(col + 1)
backtrack(row, col)
answer[row][col] = 0
end = False
if end:
return
def placeRelative(row, col):
for count in range(SIZE):
grid[row][count] += 1 #加1大大简化了问题
grid[count][col] += 1
#左下
if row + count < SIZE and col - count >= 0:
grid[row + count][col - count] += 1
#左上
if row - count >= 0 and col - count >= 0:
grid[row - count][col - count] += 1
#右上
if row - count >= 0 and col + count < SIZE:
grid[row - count][col + count] += 1
#右下
if row + count < SIZE and col + count < SIZE:
grid[row + count][col + count] += 1
def backtrack(row, col):
for count in range(SIZE):
grid[row][count] -= 1
grid[count][col] -= 1
if row + count < SIZE and col - count >= 0:
grid[row + count][col - count] -= 1
if row - count >= 0 and col - count >= 0:
grid[row - count][col - count] -= 1
if row - count >= 0 and col + count < SIZE:
grid[row - count][col + count] -= 1
if row + count < SIZE and col + count < SIZE:
grid[row + count][col + count] -= 1
def printAnswer():
for row in range(SIZE):
print answer[row]
print "\n"
if __name__ == "__main__":
placeCol(0)
受网上启发，第二版：
'''
Created on 2012-8-16
@author: yians
'''
SIZE = 92
answer = [0 for col in range(SIZE)]
def placeCol(col):
if col == SIZE:
printAnswer()
return
for row in range(SIZE):
answer[col] = row
if isValid(col):
placeCol(col + 1)
def isValid(col):
for index in range(0, col):
if (answer[index] == answer[col]):
return False
if (abs(answer[col]-answer[index]) == col - index):
return False
return True
def printAnswer():
for col in range(SIZE):
line = [0 for i in range(SIZE)]
line[answer[col]]=1
print line #output transformed answer
print "\n"
if __name__ == "__main__":
placeCol(0)
阅读(1120) | 评论(0) | 转发(0) |
