Bob - 4 months ago 37

Python Question

8-queens problem in Python.

Hi! I only start teaching Python, so could someone explain the code written below (found in the Internet)? Some pieces of the code are complicated for me. Please, explain them. Thank you. Questions are near the code.

`BOARD_SIZE = 8`

def under_attack(col, queens): # (col, queens) What is their meaning? What do I need to write it this field?

left = right = col

for r, c in reversed(queens): # What does reversed means in this loop? For what reson do we need r and c (their meaning is 0 by default?)?

left, right = left-1, right+1

if c in (left, col, right):

return True

return False

def solve(n):

if n == 0: return [[]]

smaller_solutions = solve(n-1) # For what reasons do we need to write smaller_solutions?

return [solution+[(n,i+1)] # What is solution (is it a function or what?)? What is value of i?

for i in range(BOARD_SIZE)

for solution in smaller_solutions

if not under_attack(i+1, solution)]

for answer in solve(BOARD_SIZE): print answer

Thank you!

Answer

Your code is wrong (cut and paste error?), but here's the gist:

You want a list of possible solutions. Each solution is a list of queens. Every queen is a tuple - a row (integer) and column (integer). For example, the solution for `BOARD_SIZE=1`

is `[[(1,1)]]`

- a single solution - `[(1,1)]`

containing a single queen - `(1,1)`

placed on row 1 and column 1.

There are 8 `smaller_solutions`

for `BOARD_SIZE=8`

, and `n=1`

- [[(1,1)],[(1,2)],[(1,3)],[(1,4)],[(1,5)],[(1,6)],[(1,7)],[(1,8)]] - a single queen placed in every column in the first row.

You understand recursion? If not, google it NOW.

Basically, you start by adding 0 queens to a size 0 board - this has one trivial solution - no queens. Then you find the solutions that place one queen the first row of the board. Then you look for solutions which add a second queen to the 2nd row - somewhere that it's not under attack. And so on.

```
def solve(n):
if n == 0: return [[]] # No RECURSION if n=0.
smaller_solutions = solve(n-1) # RECURSION!!!!!!!!!!!!!!
solutions = []
for solution in smaller_solutions:# I moved this around, so it makes more sense
for column in range(1,BOARD_SIZE+1): # I changed this, so it makes more sense
# try adding a new queen to row = n, column = column
if not under_attack(column , solution):
solutions.append(solution + [(n,column)])
return solutions
```

That explains the general strategy, but not `under_attack`

.

`under_attack`

could be re-written, to make it easier to understand (for me, you, and your students):

```
def under_attack(column, existing_queens):
# ASSUMES that row = len(existing_queens) + 1
row = len(existing_queens)+1
for queen in existing_queens:
r,c = queen
if r == row: return True # Check row
if c == column: return True # Check column
if (column-c) == (row-r): return True # Check left diagonal
if (column-c) == -(row-r): return True # Check right diagonal
return False
```

My method is a little slower, but not much.

The old `under_attack`

is basically the same, but it speeds thing up a bit. It looks through `existing_queens`

in reverse order (because it knows that the row position of the existing queens will keep counting down), keeping track of the left and right diagonal.