Also wollte ich das selbst mal probieren . Ich habe bis jetzt darauf verzichtet auf bereits existierende Implementierungen zu sehen, da ich von Anfang an arbeiten wollte. Meine Implementierung ist im Moment noch zu langsam und findet für N=100 keine Lösung in 1000 Schritten. Folgende Verbesserungsmöglichkeiten habe ich mir schon ausgedacht (teilweise im SC kommentiert):
- Nur Spalten zu minimieren die eine Dame enthalten mit conflicts >= 1. Im Moment suche ich einfach zufällig eine Spalte aus, welche ich dann minimiere. Das führt zu überflüssigen Schritten.
- Eine conflicts(board, row, col) Funktion die die Konflikte nur aus der Sicht einer bestimmten Dame zurückgibt.
- Beim Minimieren der Konflikte in einer Spalte bereits früher abzubrechen.
Bin gespannt auf euer Feedback.
Hier nun meine Implementierung:
Code: Alles auswählen
from random import choice, randint
import matplotlib.pyplot as plt
import numpy as np
#########################################
## Depending on the implentation of board
def setQueen(board, row, col):
board[row,col] = 1
def moveQueenAlongColumn(board, row, col):
'Move the queen in column to given row'
board[:,col] = 0
setQueen(board,row, col)
def boardSize(board):
return board.shape[0]
def createBoard(size):
return np.zeros((size,size))
def conflicts(board):
'Return number of conflicts on the board'
m = board.shape[0]
board_rotated = np.rot90(board)
ret = 0
for i in range(m):
ret += normConflicts(board[i,:].sum()) +\
normConflicts(board[:,i].sum()) +\
normConflicts(board.trace(i)) +\
normConflicts(board.trace(-i)) +\
normConflicts(board_rotated.trace(i)) +\
normConflicts(board_rotated.trace(-i))
return ret
def normConflicts(conflicts):
'Take into account that one or no queen on a line is not a conflict.'
if conflicts <= 1:
return 0
else:
return conflicts -1
##
###########################################
def populateBoard(board):
"""
Populates the board inplace with an initial good choice of queens:
There is exactly one queen in each row and column.
"""
n = boardSize(board)
availableColumns = range(n)
for row in xrange(n):
col = choice(availableColumns)
setQueen(board, row, col)
availableColumns.remove(col)
def minimalConflictsOnColumn(board, col):
'''Move the queen on the column and return the board configuration
with minimal conflicts. If ambigious return random minimal board.'''
n = boardSize(board)
conflictsVector = [] # index = row
for row in range(n):
moveQueenAlongColumn(board, row, col)
conflict = conflicts(board)
conflictsVector.append(conflict)
# Select a random row minimizing the conflicts:
minvalue = min(conflictsVector)
minrow_indices = [i for i, j in enumerate(conflictsVector) if j == minvalue]
minrow_choice = choice(minrow_indices)
moveQueenAlongColumn(board, minrow_choice, col)
def minconflicts(n, max_steps):
'Solves the n queens problem'
board = createBoard(n)
populateBoard(board)
conflicts_stats = []
for i in range(max_steps):
if conflicts(board) == 0:
break
# TODO: proposed implementation chooses a column which causes conflicts, we choose random
col = randint(0,n-1)
row = minimalConflictsOnColumn(board, col)
if conflicts(board) == 0:
print "solved in ", i , " steps."
print board
return board
else:
print "not solved"
i += 1
if __name__ == "__main__":
minconflicts(8, 1000)