8 queens problem solver

SUBMITTED BY: Guest

DATE: Dec. 31, 2013, 10 a.m.

FORMAT: Python

SIZE: 2.7 kB

Raw Download

HITS: 1151

Report
  1. import random
  2. from random import choice
  3. import sys
  5. def findConflicts(board, queen):
  6. n = len(board)
  7. conflicts = 0
  9. # W
  10. for i in range(0,queen):
  11. if(board[i] == board[queen]):
  12. conflicts += 1
  13. break
  15. # E
  16. for i in range(queen+1, n):
  17. if(board[i] == board[queen]):
  18. conflicts += 1
  19. break
  21. # NW
  22. for i in range(0,queen):
  23. if(board[i] == board[queen] + queen - i):
  24. conflicts += 1
  25. break
  27. # SW
  28. for i in range(0,queen):
  29. if(board[i] == board[queen] - queen + i):
  30. conflicts += 1
  31. break
  33. # NE
  34. for i in range(queen+1, n):
  35. if(board[i] == board[queen] - queen + i):
  36. conflicts += 1
  37. break
  39. # SE
  40. for i in range(queen+1, n):
  41. if(board[i] == board[queen] + queen - i):
  42. conflicts += 1
  43. break
  45. return conflicts
  47. def checkBoard(board):
  48. for i in range(0, len(board)):
  49. if(findConflicts(board, i) > 0):
  50. return False
  51. return True
  53. def solveBoard(board):
  54. colNames = ['a','b','c','d','e','f','g','h']
  55. steps = 10000
  56. moves = 0
  57. lastMoved = None
  58. for i in range(0, steps):
  59. if(checkBoard(board) == True):
  60. print "moves: "+str(moves)
  61. return board
  62. randQueen = random.randint(0, len(board)-1)
  64. currentConflicts = findConflicts(board, randQueen)
  65. if(currentConflicts > 0 and randQueen != lastMoved):
  66. colConflicts = []
  67. for row in range(1, len(board)+1):
  68. testBoard = list(board)
  69. testBoard[randQueen] = row
  70. colConflicts.append(findConflicts(testBoard, randQueen))
  71. minConflict = min(colConflicts)
  72. minConflictRows = [t for t, u in enumerate(colConflicts) if u == minConflict]
  73. newRow = choice(minConflictRows)+1
  74. if(board[randQueen] != newRow):
  75. print colNames[randQueen]+str(board[randQueen])+" -> "+colNames[randQueen]+str(newRow)
  76. board[randQueen] = newRow
  77. lastMoved = randQueen
  78. moves += 1
  79. return None
  81. if(len(sys.argv) >= 2):
  82. board = [int(x) for x in sys.argv[1].split(",")]
  83. else:
  84. print "missing board argument"
  85. sys.exit(0)
  87. colNames = ['a','b','c','d','e','f','g','h']
  89. boardToSolve = list(board)
  90. for i in range(len(boardToSolve)):
  91. boardToSolve[i] = colNames[i]+str(boardToSolve[i])
  92. print ",".join([str(n) for n in boardToSolve])
  95. board = solveBoard(board)
  96. if(board is None):
  97. print "Solution not found"
  98. else:
  100. for i in range(len(board)):
  101. board[i] = colNames[i]+str(board[i])
  102. print ",".join([str(n) for n in board])
comments powered by Disqus