I am trying to brute force solve the N Queen Chess Problem https://en.wikipedia.org/wiki/Eight_queens_puzzle
My code is working however unusual behaviour appears when I try and return the solution data structures.
The list containing the solutions is overwritten at some point or corrupted.
I have tried using multiple different data structures lists, dictionaries, sets and all have the same outcome.
The output should be
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
but currently is returning as
[[3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3]]
import numpy as np
# Validation Functions
def checkRows(state):
"""
Check only 1 queen per row
"""
for row in state:
if sum(row) > 1:
return False
return True
def checkCols(state):
"""
Check only 1 queen exists in a column
"""
for i in range(0,len(state)):
count = 0
for j in range(0,len(state)):
#print(state[j][i])
count = count + state[j][i]
if count > 1: return False
return True
def checkDiag(state):
"""
Checks only 1 queen exists per diagonal
https://stackoverflow.com/questions/6313308/get-all-the-diagonals-in-a-matrix-list-of-lists-in-python
"""
# Alter dimensions as needed
n = len(state)
x,y = n,n
# incoming state list
a = np.array(state)
diags = [a[::-1,:].diagonal(i) for i in range(-a.shape[0]+1,a.shape[1])]
diags.extend(a.diagonal(i) for i in range(a.shape[1]-1,-a.shape[0],-1))
for n in diags:
if sum(n) > 1: #if any of the diagonals sums to more than 1 there must be more than 1 queen in that diagonal
return False
return True
def checkState(state):
"""
Returns false on one or more failures
"""
return checkRows(state) and checkCols(state) and checkDiag(state)
def worker_translate(dim, sol):
"""
Translate from the permutations function to a format to be checked by validation functions
"""
state = []
for val in range(dim - 1, -1, -1):
inner_list = []
for y in sol:
if y == val:
inner_list.append(1)
else:
inner_list.append(0)
state.append(inner_list)
return state
def print_solution(dim, sol):
for val in range(dim - 1, -1, -1):
for y in sol:
if y == val:
print('Q ', end='')
else:
print('. ', end='')
print()
print()
def runner(x):
# go through the permutations searching for all possible solutions
dim = int(x)
# populate this_permutation
this_permutation = []
for n in range(dim):
this_permutation.append(0)
# calculate the number of permutations
possible_permutations = dim**dim
# for n in range(dim):
# possible_permutations *= dim
mydict = {}
mylist = []
# iterate through all possible permutations
for n in range(possible_permutations):
rem = n
for m in range(dim):
this_permutation[m] = rem % dim
rem //= dim
res = checkState(worker_translate(dim, this_permutation))
if res:
#print("Solution Found")
#print(this_permutation)
#print(worker_translate(dim, this_permutation))
#print_solution(dim, this_permutation)
mylist.append(this_permutation)
mydict[n] = this_permutation
print(mydict)
print(mylist)
print("data structures not working after this point")
print(mydict)
print(mylist)
return(mydict,mylist)
print(runner(4))
The output from compiled code
{114: [2, 0, 3, 1]}
[[2, 0, 3, 1]]
{114: [2, 0, 3, 1]}
[[2, 0, 3, 1], [2, 0, 3, 1]]
{114: [2, 0, 3, 1]}
[[2, 0, 3, 1], [2, 0, 3, 1], [2, 0, 3, 1]]
{114: [2, 0, 3, 1]}
[[2, 0, 3, 1], [2, 0, 3, 1], [2, 0, 3, 1], [2, 0, 3, 1]]
{114: [1, 3, 0, 2], 141: [1, 3, 0, 2]}
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
{114: [1, 3, 0, 2], 141: [1, 3, 0, 2]}
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
{114: [1, 3, 0, 2], 141: [1, 3, 0, 2]}
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
{114: [1, 3, 0, 2], 141: [1, 3, 0, 2]}
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
data structures not working after this point
{114: [3, 3, 3, 3], 141: [3, 3, 3, 3]}
[[3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3]]
({114: [3, 3, 3, 3], 141: [3, 3, 3, 3]}, [[3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3]])
Process finished with exit code 0
See Collin Heist's answer in the comments for explanation.
mylist.append(this_permutation.copy())