

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

The N-Queens-Problem as a CSP

The function create_csp(n) takes a natural number n as argument and returns a constraint satisfaction problem that encodes the n-queens puzzle.

A constraint satisfaction problem $\mathcal{P}$ is a triple of the form $$ \mathcal{P} = \langle \mathtt{Vars}, \mathtt{Values}, \mathtt{Constraints} \rangle $$ where

$\mathtt{Vars}$ is a set of strings which serve as variables.

The idea is that $V_i$ specifies the column of the queen that is placed in row $i$.
$\mathtt{Values}$ is a set of values that can be assigned to the variables in $\mathtt{Vars}$.

In the 8-queens-problem we will have $\texttt{Values} = \{1,\cdots,8\}$.
$\mathtt{Constraints}$ is a set of formulas from first order logic.
Each of these formulas is called a constraint of $\mathcal{P}$.



In [ ]:

    
def create_csp(n):
    S              = range(1, n+1)           
    Variables      = { f'V{i}' for i in S }
    Values         = set(S)
    DifferentCols  = { f'V{i} != V{j}' for i in S
                                       for j in S
                                       if  i < j 
                     }
    DifferentDiags = { f'abs(V{j} - V{i}) != {j - i}' for i in S
                                                      for j in S 
                                                      if  i < j 
                     }
    return Variables, Values, DifferentCols | DifferentDiags

The function main() creates a CSP representing the 4-queens puzzle and prints the CSP. It is included for testing purposes.



In [ ]:

    
def main():
    Vars, Values, Constraints = create_csp(4)
    print('Variables:  ', Vars)
    print('Values:     ', Values)
    print('Constraints:')
    for c in Constraints:
        print('            ', c)



In [ ]:

    
main()

Displaying the Solution

In order to have a more convenient view of the solution of the 8 queens puzzle, we have to install python-chess. After activating the appropriate Python environment, this can be done using the following command:

   pip install python-chess



In [ ]:

    
import chess

The function show_solution(Solution) takes a dictionary that contains a variable assignment that represents a solution to the 8-queens puzzle. It displays this Solution on a chess board.



In [ ]:

    
def show_solution(Solution):
    board = chess.Board(None)  # create empty chess board
    queen = chess.Piece(chess.QUEEN, True)
    for row in range(1, 8+1):
        col = Solution['V'+str(row)]
        field_number = (row - 1) * 8 + col - 1
        board.set_piece_at(field_number, queen)
    display(board)



In [ ]: