Question

# Parts to be completed are marked with '<<<<< COMPLETE'
import random

N = 8
MAXSTEPS = 5000

# generates a random n-queens board
# representation: a list of length n the value at index i is
# row that contains the ith queen;
# exampe for 4-queens: [0,2,0,3] means that the queen in column 0 is
# sitting in row 0, the queen in colum 1 is in row, the queen in column 2
# is in row 0, and the queen in column 3 is in row 3;
def random_queens(n):
queens = []
for i in range(n):
queens.append(random.randint(0,n-1))
return queens

# displays the n-queens board as indicated by list qs
# example for 4-queens: [0,2,0,3] prints out as
#
# Q _ Q _
# _ _ _ _
# _ Q _ _
# _ _ _ Q ... notice queens conflicts that need repair ...

def show_nqueens(qs):
for row in range(len(qs)):
for col in range(len(qs)):
if row == qs[col]:
print 'Q',
else:
print '_',
print ""
return

# prints out the coordinates [row,col] for each queen on the board
# represented by list qs;

def queens_coords(qs):
coords = []
for col in range(len(qs)):
coords.append([qs[col],col])
return coords

# how many queens are in row k?
# = how many times does k appear in qs list?
# for the queens board [0,2,0,3] and each row, you get
#
# queens in row 0: 2
# queens in row 1: 0
# queens in row 2: 1
# queens in row 3: 1

def queens_in_row(k,qs):
return qs.count(k)

# returns how many queens are in diagonals 1 and 2 going through cell (row,col);
# also counts the queen that may be sitting in exactly (row,col)

#NEW VERSION 2/16, 7pm
def queens_in_diags1(row,col,qs):
k = 0
for r in range(len(qs)):
for c in range(len(qs)):
if (row - r) == (col - c):
if qs[c] == r:
k += 1
return k

def queens_in_diags2(row,col,qs):
k = 0
for r in range(len(qs)):
for c in range(len(qs)):
if (row - r) == -(col - c):
if qs[c] == r:
k += 1
return k

# combines diagonal conflicts and removes double counting for fields
# that have a queen;

def queens_in_diags(row,col,qs):
qd1 = queens_in_diags1(row,col,qs)
qd2 = queens_in_diags2(row,col,qs)
if qs[col] == row:
return qd1 + qd2 - 1
else:
return qd1 + qd2

# WARNING: When using any of the queens_in_diagsX functions, be aware of
# which one(s) have double counts (with likely need to compensate later) in
# their return values and which one(s) do not; both variants can be used, but
# you need to be aware of the implications of your choice down the line; program
# accordingly;

# given a column number (col) and the queens board qs, returns the
# number of conflicts in this colum for each row;
# for column 0 of queens board [0,2,0,3] which prints as
#
# Q _ Q _
# _ _ _ _
# _ Q _ _
# _ _ _ Q
#
# you get conflicts [3,1,2,2,] in rows 0..3 of col 0;

# NEW VERSION, 02/16, 7:14pm

def column_conflicts(col,qs):
rowsqs = map(lambda r: queens_in_row(r,qs),range(len(qs)))
#print rowsqs
diags1qs = map(lambda r: queens_in_diags1(r,col,qs), range(len(qs)))
#print diags1qs
diags2qs = map(lambda r: queens_in_diags2(r,col,qs), range(len(qs)))
#print diags2qs
confs = map(lambda x,y,z: x+y+z, rowsqs,diags1qs,diags2qs)
#print confs
# if a queen sits in field [r,col], then this field has been
# counted as threatened 3x by this one queen: via the row, and
# via both diagonals; adjust by subtracting 2; one queen is one "threat" to its own field;
for r in range(len(qs)):
if qs[col] == r:
confs[r] -= 2
#print confs
return confs

# returns the row index of the field in column numbered 'col' that is
# threatened by the smallest number of queens; for the above example
# with conflicts [3,1,2,2,] in rows 0..3 of col 0, this function returns
# row index 1 (field (1,0), row 1 in col 0, is threatened by the minimal number
# of queens, here: 1;
def min_conflicts_row(col,qs):
conf = column_conflicts(col,qs)

#<<<< COMPLETE (1)

return # replace as appropriate

# change qs so that the queen in column col is in row 'row; unless it already is
def column_repair(col,row,qs):
qs[col] = row
return

# returns True if there is at most one queen in every row and diagonal; False
# otherwise; (by virtue of the representation, it is a given that each column contains
# a single queen; thus no need to test for columns);
def queens_solved(qs):

#<<<<< COMPLETE (2)

return # replace as appropriate
  
def hrepair(queens):
step = 1
print "Heuristic Repair of:\n"
show_nqueens(queens)
print "\n\n"
while True:
if queens_solved(queens):
# <<<<< COMPLETE (3)
pass # place holder; remove/replace as appropriate
  
if step > MAXSTEPS:
# <<<<< COMPLETE (4)
pass # place holder; remove/replace as appropriate
  
for i in range(len(queens)):
targetrow = min_conflicts_row(i,queens)
print "[%d] col %d: min conflicts in row %d" % (step,i,targetrow)

# <<<<< COMPLETE (5)
  
step += 1
return

'''
# uncomment for later testing and demo ...

def main():
n = int(raw_input("How many queens: "))
qs = random_queens(n)
hrepair(qs)

if __name__ == "__main__":
main()
  
'''

Answer 1