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.
Z.B ist es in Ordnung dass ich die Funktionen quasi nur mit Side Effects baue (weil board := numpy.array ja mutable ist) oder soll man das ganze funktionaler bauen? Ist der Code gut lesbar, wenn nein was könnte ich daran ändern um es zu verbessern?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)