import unittest from sys import argv \'\'\' The eight queens puzzle is the probl
ID: 3918140 • Letter: I
Question
import unittest from sys import argv ''' The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3. https://en.wikipedia.org/wiki/Eight_queens_puzzle ''' # start with solving this SOLVE_ONE = True # then worry about this if you have time SOLVE_ALL = True def safe(x1, y1, x2, y2): return not (x1 == x2 or y1 == y2 or abs(x2-x1) == abs(y2-y1)) def print_board(solution): length = len(solution) print('-' * length) a = [['Q' if (i, j) in solution else '.' for j in range(length)] for i in range(length)] for i in a: print(''.join(i)) print('-' * length) ''' size is the overall size of the problem we're solving. row is the row we're currently on, starting with 0. placed is a list of queens -- a list of tuples with (x,y) -- that have already been placed on the board. ''' def solve_one(size, row, placed): # if we're past the last row, return placed as it has the answer. # for each column # see if placing a queen at row and column is safe from all placed # queens. # if it is safe # make a recursive call with the next row and placed + (row, column) # if there was a solution with those parameters, return it. # return the empty list pass ''' as above, but accumulate all the solutions in the last argument. ''' def solve_all(size, row, placed, solutions): pass class test_safe(unittest.TestCase): def test_same(self): self.assertFalse(safe(1, 1, 1, 1)) def test_same_row(self): self.assertFalse(safe(1, 1, 1, 2)) def test_same_column(self): self.assertFalse(safe(1, 1, 2, 1)) def test_same_diagonal(self): self.assertFalse(safe(1, 1, 5, 5)) class test_one(unittest.TestCase): def test_one_one(self): self.assertEqual(solve_one(1, 0, []), [(0, 0)]) def test_two_all(self): self.assertEqual(solve_one(2, 0, []), []) def test_four_one(self): self.assertEqual(solve_one(4, 0, []), [(0, 1), (1, 3), (2, 0), (3, 2)]) ''' class test_all(unittest.TestCase): def test_one_all(self): self.assertEqual(solve_all(1, 0, [], []), [[(0, 0)]]) def test_two_all(self): self.assertEqual(solve_all(2, 0, [], []), []) def test_three_all(self): self.assertEqual(solve_all(3, 0, [], []), []) def test_four_all(self): solutions = solve_all(4, 0, [], []) self.assertEqual(solutions, [[(0, 1), (1, 3), (2, 0), (3, 2)], [(0, 2), (1, 0), (2, 3), (3, 1)]]) ''' if __name__ == "__main__": size = 8 if len(argv) == 1 else int(argv[1]) if SOLVE_ONE: print_board(solve_one(size, 0, [])) if SOLVE_ALL: solutions = [] solve_all(size, 0, [], solutions) print("there are", len(solutions), "solutions for the", size, "queens problem:") for solution in solutions: print_board(solution)
Explanation / Answer
import copy
import time
solution_set = {}
N_QUEENS = 8
class GameState(object):
def __init__(self):
self.board = [[0 for x in range(N_QUEENS)] for y in range(N_QUEENS)]
self.num_queens = 0
def __repr__(self):
return ' '.join([''.join(['Q' if self.board[x][y]==1 else '.' if self.board[x][y]==-1 else '.' for x in range(N_QUEENS)]) for y in range(N_QUEENS)])
def get(self, x, y):
return self.board[x][y]
def solve(self):
for x in range(N_QUEENS):
for y in range(N_QUEENS):
if self.board[x][y] == 1:
new_state = copy.deep_copy(self)
new_state.place_queen(x, y)
return new_state.solve()
def place_queen(self, x, y):
assert x in range(N_QUEENS) and y in range(N_QUEENS) and not self.board[x][y]
self.board[x][y] = 1
self.num_queens += 1
# update valid remaining spaces
# TODO this can be optimized
for i in range(N_QUEENS):
if not self.board[i][y]:
self.board[i][y] = -1
if not self.board[x][i]:
self.board[x][i] = -1
if x+i in range(N_QUEENS) and y+i in range(N_QUEENS) and not self.board[x+i][y+i]:
self.board[x+i][y+i] = -1
if x-i in range(N_QUEENS) and y-i in range(N_QUEENS) and not self.board[x-i][y-i]:
self.board[x-i][y-i] = -1
if x-i in range(N_QUEENS) and y+i in range(N_QUEENS) and not self.board[x-i][y+i]:
self.board[x-i][y+i] = -1
if x+i in range(N_QUEENS) and y-i in range(N_QUEENS) and not self.board[x+i][y-i]:
self.board[x+i][y-i] = -1
def copy(self):
s = GameState()
s.board = copy.deepcopy(self.board)
s.num_queens = self.num_queens
return s
def solve(state=GameState()):
if state.num_queens == N_QUEENS: # Base condition
#print 'Solution found:'
#print state
sol = str(state)
if sol not in (solution_set):
solution_set[str(state)] = None
print sol + ' '
else: # Time to recurse
for x in range(N_QUEENS):
for y in range(N_QUEENS):
if not state.get(x,y):
new_state = state.copy()
new_state.place_queen(x, y)
solve(new_state)
start_time = time.time()
solve(GameState())
#for sol in solution_set.keys():
# print sol + ' '
print '%d unique solutions found.' % len(solution_set.keys())
print 'Elapsed time: %.3fs' % (time.time() - start_time)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.