Eight Queens Puzzle

In my artificial intelligence (AI) class last semester I learned about different categories of mathematical problems that can be solved effectively using methods applied in modern AIs. One category contained constraint satisfaction problems (CSPs). As the name loosely implies, these problems give you variables that can have different states and a set of constraints, that have to be satisfied by the states of the variables. The difficult part of these problems is to find a state combination that solves the CSP without considering too many possibilities, which otherwise could quickly make the calculation too large (and computationally unfeasible).

Eight Queens Puzzle

One of the best examples for a CSP is the eight queens puzzle. It is a mathematical problem formulated using the rules of chess. Your goal is to place eight queens on a standard eight by eight chess board without any two queens threatening each other, meaning that a queen could take another queen in the next turn. Here are the directions a queen can attack on a chess board:

• the queen can move horizontally on the chessboard
• the queen can move vertically on the chessboard
• the queen can move diagonally in any direction on the chessboard

After trying the eight queens puzzle with my brother out on a standard chess board (by the way: he solved it in under 10 minutes), we quickly noticed that one of the harder aspects when trying to solve the eight queens puzzle is simply to recognize if the current placement is even a valid one, where no two queens threaten each other. You often forget to check the long diagonal directions of each queen.

I decided to create a web version of the eight queens puzzle only using JavaScript making it playable on most browsers (mobile and desktop), that incorporates a view, that shows you where you can’t place another queen on the board according to your current queen placement.

So that I don’t have to create everything from scratch, I used EaselJS, which is a JavaScript library for working with the canvas element. This is a very lightweight solution to create simple web games and the documentation and user support was good enough, so that I didn’t get stuck too often during development. But like most times when developing something new, you underestimate how much time it would take to finish the project. I estimated only needing around 150 lines of code and one afternoon to get it done, but it ended up being a few days and around 300 lines of code.

8 Queens Puzzle Web Game

So this is my final game. You can go ahead and try to place eight queens onto the chessboard. Queens are placed by clicking (or tapping when you’re on a touchscreen) the tile you want to place your next queen on. You can press the UNDO button to remove the last placed queen. A red tile means, that this tile is being threatened by an already placed queen, so you can’t place your next queen there anymore.

You need a Frames Capable browser to view this content.

I really noticed from playing it with the red tiles showing you invalid positions, it is easier to come up with a solution just by guessing. If you had the same experience, here is another version of the game, only the red tiles aren’t displayed anymore and you only get a warning message when you try to place a queen at a threatened position. This is considerably harder and gives you an experience closer to actually trying the puzzle out on a real chessboard:

You need a Frames Capable browser to view this content.

So now that we know, that we humans can solve the eight queens puzzle, let us see how CSPs can be solved using Python.

Solving CSPs in Python

Now I am certainly no expert on how so-called “CSP solvers” are written, but I know that logical methods like resolution are used to simplify the problem to a degree. From there on clever heuristics are used, that make it more probable for you to find a solving solution faster. You have to define the variables and the constraints, but the actual calculation is going to be a black box for us in this case.

I found a module called python-constraint, that offers us a CSP resolver written in Python. The module’s web page also shows some additional examples for puzzles that can be solved as a CSP. It’s really straightforward to use, although it seems to only work with Python 2 (not 3) so be aware of that.

In a CSP there are variables that can hold certain values (sometimes called states) and constraints that have to be held by the variables. The set of values that a variable can be assigned with is also called its domain. A constraint is a logical expression that has to hold. Now lets see how we can describe the eight queens puzzle as a CSP.

First we are going the define our variables and their respective domains. The most intuitive approach is to have one variable describe the position of one queen on the chessboard. So we are going to need a total of eight variables. In our solution (that I found here on stackoverflow) we are going to name each variable (/queen) as a number and this will describe the column in which this queen is placed, so the number is in the range from 1 to 8. We can do this, since a column uniquely describes one queen, since two queens in the same column would threaten each other. The actual value of each variable will then describe the row in which the queen is placed. This means that each variable has a domain of the natural numbers between 1 and 8. This is how it looks written in Python code using python-constraint:

from constraint import *

problem = Problem()
cols = range(1,9) # these are the variables
rows = range(1,9) # these are the domains
problem.addVariables(cols, rows) # adding multiple variables at once

The next step is to add our constraints. In the eight queens puzzle the overall constraint is that no two queens should threaten each other. But since we have to write our constraints as logical expressions, let’s divide the different moves of the queen as separate constraints. So we are going to loop through our list of queens and add constraints to each pair of different queens. Let’s first look at the code and then see what was done here:

We are adding constraints between each pair of two queens saying, that are not allowed to meet up diagonally, described by this clever comparison of the absolute difference between the row and column of each queen. The second part of the logical expression makes sure, that no two queens are in the same row. And this then outputs us the following solution:

{1: 8, 2: 4, 3: 1, 4: 3, 5: 6, 6: 2, 7: 7, 8: 5}

The first number describing the column and the second one the row of a queen (although this also can be swapped as long as it is done consistently). And if you try this out on the game on top, you will notice that this is a valid solution to the eight queen puzzle.

Here is a gist to the JavaScript code for the queen game and the full script for the python CSP solution.

If you have any questions regarding me or this post, then just write a comment in the section below. And if you enjoy reading my content I suggest you to sign up to my Rather Read Newsletter, where I will notify you about every new post as well as about recent books, articles, artists that I discovered in the past few weeks.

Thank you for reading, have a nice week!

The post Eight Queens Puzzle appeared first on Rather Read.