<a href="https://colab.research.google.com/github/ContextLab/psyc32-n-queens/blob/main/n-queens.ipynb" target="_parent"></a>

# The $n$-Queens puzzle: Introduction and overview

The classic [eight queens puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle) refers to the challenge of placing eight [chess](https://en.wikipedia.org/wiki/Chess) [queens](https://en.wikipedia.org/wiki/Queen_(chess)) on an $8 \times 8$ board such that no queen is attacking any other.  Specifically, there can only be (at most) a single queen on any row, column, or diagonal of the board.  Here is one solution to the eight queens puzzle (there are 92 distinct solutions in total, or 12 if rotations and reflections are not counted as separate solutions):



In principle, the eight queens puzzle may be generalized to imaginary chessboards of any size.  For $n \geq 1$, placing $n$ queens on an $n \times n$ chess board is referred to as the $n$-queens puzzle.

For this assignment, you'll be building a solver for the $n$-queens puzzle.  There are two general functions you'll need to write:
1. A function for printing out a board position (e.g., depicting the configuration of the pieces visually)
2. A function for checking whether a given position corresponds to a solution (i.e., whether any queens are attacking each other)

Using these two functions, you'll be provided with functions for returning all solutions (given $n \geq 1$) and for returning the *number* of solutions (given $n \geq 1$).

## Some history of the $n$-queens puzzle
In [this 2017 paper](https://www.jair.org/index.php/jair/article/view/11079), the $n$-queens puzzle (also called the $n$-queens problem) was shown to be a member of a set of problems in computer science that are [NP-complete](https://en.wikipedia.org/wiki/NP-completeness).  Exploring or proving NP-completeness is beyond the scope of our course, but the super high-level intuition for NP-completeness may be summarized as follows:
  - For all known ways of solving them, NP-complete problems take a very long time to solve (their associated computations don't scale well).  NP stands for "nondeterministic polynomial".  The "polynomial" part refers to how many computations it takes to solve the problem and verify its solution as a function of the size of the problem (e.g., the '$n$' in the $n$-queens puzzle).  The "nondeterministic" part means that there's no known direct (deterministic) strategy or set of rules that can be followed to generate a solution.
  - Because all NP-complete problems can be efficiently(ish) converted to other NP-complete problems, solving any one NP-complete problem efficiently would also provide an efficient solution for *all* NP-complete problems.

Solving NP-complete problems efficiently (or even proving whether or not NP-complete problems *can* be solved efficiently) is an [open question in computer science](https://en.wikipedia.org/wiki/P_versus_NP_problem).  Even early on in your journey towards learning to program, it can still be fun and instructive to explore problems like the $n$-queens puzzle.  Before reading the next section, where I'll present the way of solving the puzzle that we'll be using in this assignment, it's worth taking a few moments to think about how *you* might go about solving it.  For example:
  - How might you represent the chess board using some of the Python datatypes that you've already learned about?
  - How might you represent the positions of the pieces (queens) on the board?
  - How might you go about systematically generating "guesses" about possible solutions?
  - How might you go about *checking* whether a particular guess is a valid solution?

I encourage you to sketch out some thoughts and/or [discuss](https://gitter.im/cs-for-psych/PSYC-132-Winter-2021) with classmates.

# General (naïve-ish) solution

**(Spoiler alert!)**

First, we'll represent the board in an efficient way: an $n$-element list, where the position reflects the column number and the value reflects the row of the queen at that column.

For example, the above solution to the 8-queens puzzle could be represented by the list [1, 3, 5, 7, 2, 0, 6, 4].  Make sure you understand why that particular list corresponds to that particular position before moving on.  (Hint: remember that positions are [zero-indexed](https://en.wikipedia.org/wiki/Zero-based_numbering) in Python.)  Try writing out the board positions for some other lists of different lengths-- e.g. [0, 3, 1, 2] or [4, 3, 2, 1, 0], etc.

Notice that, with this notation, every possible solution to the $n$-queens puzzle must be a permutation of the integers from 0 to $n-1$. This ensures that at most a single queen is placed in each row and column.  As long as there are no repeated numbers in the list, we know that no queens are attacking each other vertically or horizontally (since each list element only has one number).

Next we need to check for diagonal attacks. Using the same notation, we can check to see if queens are attacking each other along a "forward" (top-left to bottom-right) diagonal by asking whether any queens share the same difference between their row and column. In other words: if $r_0...(n-1)$ represents the queens' rows and $c_0...(n-1)$ represents the queens' columns, we must ensure that $r_i - c_i$ never equals $r_j - c_j$ for any value of $i \neq j$. This can be checked efficiently by ensuring that `len(np.unique(np.arange(n) - pos)) == n`. Finally, to check the "reverse" diagonals (i.e. top-right to bottom-left), we can use analogous logic and verify that `len(np.unique(np.arange(n-1, -1, -1) - pos)) == n` as well.

If no queens share a row, column, forward diagonal, or reverse diagonal, and if $n$ queens have been placed on the $n \times n$ board, then we have found a solution!

Naïvely, to find every solution of the $n$-queens puzzle for a given $n$, we could simply iterate through all possible permutations of the integers from $0...(n-1)$, check whether each is a valid solution, and collect up all of the permutations that are valid solutions. The challenge is that the number of permutations of $n$ numbers is $n$ factorial (i.e., $n!$), which becomes intractable as $n$ gets large. For example, storing a single integer in short (16 [bit](https://en.wikipedia.org/wiki/Bit)) format requires 2 [bytes](https://en.wikipedia.org/wiki/Byte). Therefore storing a single position (of length $n$) requires $2n$ bytes. Storing all possible $n!$ permutations for a $13 \times 13$ board would require over 12[GB](https://en.wikipedia.org/wiki/Gigabyte) of memory, and for a $14 \times 14$ board would require over 174GB!

Since our main objective for this assignment is to practice and improve our programming skills, we won't worry about scalability here-- you can safely assume that you'll never need to solve (or count solutions for) $n > 12$.

# Grading

This assignment is worth a total of 5 points.  You may view the tests in the public rubric [here](https://github.com/ContextLab/cs-for-psych/blob/master/assignments/n-queens/public_rubric.xls).  To get full credit, you must (correctly) fill in all of the code between the commented `### BEGIN YOUR CODE` and `### END YOUR CODE` blocks throughout this notebook.  (No other code should be modified.)


```
import numpy as np #the numpy library is used to represent and manipulate ordered sets (think of them like fancy lists)
from sympy.utilities.iterables import multiset_permutations #this is used to compute every permutation of a list
```

# Represent a board position as a string: `board2str`

We'll write a function to convert a board position to a string that may be printed out:
```python
>> print(board2str([0, 4, 7, 5, 2, 6, 1, 3]))

-|0|1|2|3|4|5|6|7|
0|*|-|-|-|-|-|-|-|
1|-|-|-|-|-|-|*|-|
2|-|-|-|-|*|-|-|-|
3|-|-|-|-|-|-|-|*|
4|-|*|-|-|-|-|-|-|
5|-|-|-|*|-|-|-|-|
6|-|-|-|-|-|*|-|-|
7|-|-|*|-|-|-|-|-|
```

Some things to note:
  - The `board2str` function takes as input a single argument, `pos`, which is a list representation of the board position
  - From this list representation, the function automatically determines how large the board is (`n = len(pos)`)
  - The rows and columns of the board are numbered (starting with 0)
  - Empty squares are denoted by `-` and queens are denoted by `*`
  - Rows are separated using the [newline character](https://www.freecodecamp.org/news/python-new-line-and-how-to-python-print-without-a-newline/), `\n`.  This tells Python that a single string occupies several lines, e.g. when it is printed out.

Given the input `[0, 4, 7, 5, 2, 6, 1, 3]`, `board2str` should return the following string:
```python
>> board2str([0, 4, 7, 5, 2, 6, 1, 3])

'-|0|1|2|3|4|5|6|7|\n0|*|-|-|-|-|-|-|-|\n1|-|-|-|-|-|-|*|-|\n2|-|-|-|-|*|-|-|-|\n3|-|-|-|-|-|-|-|*|\n4|-|*|-|-|-|-|-|-|\n5|-|-|-|*|-|-|-|-|\n6|-|-|-|-|-|*|-|-|\n7|-|-|*|-|-|-|-|-|'
```
Compare this to the printout above to get a feel for how it works.


```
def get_n(pos): #given a board position, compute the board size
  ### BEGIN YOUR CODE
  return 0
  ### END YOUR CODE

def board2str(pos):
  def row2str(c):
    #print out a single row with a queen in column c
    #e.g. row2str(0) should return the string '|*|-|-|-|-|-|-|-|'

    ### BEGIN YOUR CODE
    return ''
    ### END YOUR CODE
  
  def top_row(n):
    #print out the top row of labels, given the board size
    #e.g. top_row(3) should return '-|0|1|2|'

    ### BEGIN YOUR CODE
    return ''
    ### END YOUR CODE
  
  n = get_n(pos)
  board = [top_row(n)]
  for r in range(n):
    ### BEGIN YOUR CODE
    #compute the column containing the queen in row r.
    #hint: check out the np.where function
    c = 0
    ### END YOUR CODE
    board.append(str(r) + row2str(c))
  
  return '\n'.join(board)
```

# Check whether a position is a solution: `is_solved`




```
def is_solved(pos):
  n = get_n(pos)

  #check rows
  #hint: the columns are *always* unique, because of how the positions are
  #represented. how can you check whether the queens from different columns
  #occupy the same row?  you may find it useful to check out the np.unique
  #function!
  ### BEGIN YOUR CODE
  unique_rows = False
  ### END YOUR CODE

  #check forward and backward diagonals
  #hint: see the suggestions written out above in the "General (naïve-ish)
  #solution" section
  ### BEGIN YOUR CODE
  unique_forward_diagonals = False
  unique_backward_diagonals = False
  ### END YOUR CODE

  #return True if pos is a solution and False otherwise
  return unique_rows and unique_forward_diagonals and unique_backward_diagonals
```

# Solving the puzzle!

Now the fun part-- we can use your work in the cells above to solve the $n$-queens puzzle.  We'll churn through every possible permutation of the numbers $0...(n-1)$, check whether each of these "positions" is a valid solution to the $n$-queens puzzle, and keep track of all of the corresponding permutations (i.e., that checked out as valid solutions).


```
def get_solutions(n):
    solutions = []
    for p in multiset_permutations(np.arange(n).astype('int16')):
        if is_solved(p):
            solutions.append(p)
    return solutions

def count_solutions(n):
    return len(get_solutions(n))
```

# Sanity checks

Let's check that this works for the 8-queens puzzle (there should be 92 solutions)


```
eights = get_solutions(8)
print(f'Found {count_solutions(8)} solutions!')
```

And let's also print out one of the solutions; you should get the printout shown below:
```
-|0|1|2|3|4|5|6|7|
0|*|-|-|-|-|-|-|-|
1|-|-|-|-|-|-|*|-|
2|-|-|-|-|*|-|-|-|
3|-|-|-|-|-|-|-|*|
4|-|*|-|-|-|-|-|-|
5|-|-|-|*|-|-|-|-|
6|-|-|-|-|-|*|-|-|
7|-|-|*|-|-|-|-|-|
```


```
try:
    print(board2str(eights[0]))
except:
    pass
```

cf4b5d9e82c0431f4da361503ef0c01ecf98f42f
ipynb
Jupyter Notebook
n-queens.ipynb
ContextLab/psyc32-n-queens
0ac425473874a098bd9c9b269598222a9ce6f960
MIT
n-queens.ipynb
ContextLab/psyc32-n-queens
0ac425473874a098bd9c9b269598222a9ce6f960
MIT
n-queens.ipynb
ContextLab/psyc32-n-queens
0ac425473874a098bd9c9b269598222a9ce6f960
MIT
2021-01-11T19:11:15.000Z
2021-01-11T19:11:15.000Z
Qwen/Qwen-72B
1. YES
2. YES