Two classic chess problems and how to solve them (the hard way)

A few years ago when I started to teach myself programming, I was almost entirely dependent on blogs like this one. When it comes to practical stuff, learning from a textbook just doesn’t do it for me; I have to see how someone else did it. I wrote the scripts used in this post a couple of years ago so I thought it’d be quite fun to go back and revisit them…turns out I’d have solved at least one of the problems completely differently now.

Both problems here are absolute classics that any computing graduate will be familiar with. I like to imagine somewhere in the world a computer science student will stumble across this page one day and it’ll help him/her out!

 

Problem 1 – The Eight Queens

This is a dead simple problem but it’s one I’ve never been able to do without a computer (I’m terrible at chess). All it calls for is for eight Queens to be placed on the board with no pair of queens attacking one-another. For those unfamiliar, a queen can move any distance along the board both up-down and diagonally – like this:

 

queens

Three queens on the board with all their possible moves shown. Here, the green and blue queens are attacking each other while the red queen is not under attack. Just looking at this it is easy to see why it is difficult to place 8 queens on a board with none under attack.

This is exactly the sort of problem I’ve always been pretty awful at figuring out. I’m even worse these days because I just write a script to do anything like this now. As you can probably imagine, it makes me an absolute blast at parties.

 

That one weird trick – Recursion

As with most computing problems, there are loads of ways to solve this one. The simplest (excluding brute force, which would take impractically long to run) is probably to use recursion.

Recursion makes absolutely no sense until you use it a few times, then it kind of just clicks. I find it hard to give a good definition because I’m past the point where it clicked for me so it just feels kind of intuitive now, but here it goes:

A recursive function is a function that either uses itself as an input, or produces a trivial solution, depending on the initial input.

I’m not sure how helpful that was so let’s do an example. Many readers will have heard of the factorial operator – written as ‘!’. Applying this operator to a number, n, means we do this:

n! = n X (n-1) X (n-2) X … 1

So, 3! = 3 X 2 X 1

Simple, but it can also be defined completely differently using recursion. We can say the following:

IF n > 0:   n! = n X (n-1)! 

ELSE   n!=1

This looks weird – the definition contains the operator itself. It looks like a circular reference. But, the second condition (IF n=1, n!=1) breaks this deadlock. Let’s look at how we’d do this for 3!

n=3

So, using the recursive definition, n! = n X (n-1)! = 3 X 2!

But, what is 2! ? Well, we use the definition again:

n>0, so 2! = 2 X (2-1)! = 2 X 1!

But what is 1!. Use the definition again:

n>0, so 1! = 1 X 0!

Ah, the definition states that 0! = 1. Now we work back up again:

We know 0! = 1,  so 1! = 1X 0! =1

Now that we know 1! = 1,  2! = 2 X (1)! = 2

Now that we know 2! = 2,  3! = 3 X (2)! = 6

Problem solved. So, although it seems counter-intuitive, the definition of an operator can absolutely contain the operator itself, as long as we can work down to a trivial case (0!=1 in the above example). We simply ‘stack up’ the unsolved intermediate solutions, and come back to them once we have solved the trivial solution. It is actually called a stack when applied by a computer. Ever heard of ‘stack overflow’? That’s when you write a problem with excessively deep (often infinite) recursion so your stack size exceeds the available memory.

Anyway, now that we know how recursion works, the 8 queens problem is kind of easy. In fact, finding every solution is just as easy as finding just one. Let’s just do exactly what we did for the factorial function:

Let’s state that there is some function which gives all possible solutions for a 8 X 8 grid. Let’s call the function ‘finder’.

All solutions for an 8X8 grid may be found by taking each possible solution for a 7 X 8 grid and adding a new row. Then we try a queen on each of the new squares and any solutions where the new queen is not attacked are valid 8X8 grid solutions. Like this:

ezgif.com-gif-maker (1)

We do this for every valid 7X8 solution – add a new row and try a queen on every new square. Every time the queen isn’t attacked we have a valid solution.

But how do we find all the valid 7X8 grid solutions? We just add a new row to the valid 6X8 solutions as we did above. We repeat this for a 5X8 grid, then a 4X8 grid….and carry on until we get to a zero sized grid. The zero sized grid is our trivial solution and we just say the solution is an empty set. And we then work back up – we add a new row to an empty grid and place a queen on each square in turn. This will give 8 valid solutions which we save. Then we add a new row and repeat, saving all the valid solutions. We repeat until we get back to an 8X8 grid. So, to define our finder function:

IF n>0:

finder for an nXn grid = append new row onto finder for an n X (n-1) grid

ELSE finder = []

*'[]’ means an empty set

This only took 18 lines of Python code to execute, including the definition of whether a queen is under attack and gives all 92 valid solutions. The actual recursive function required just 9 lines – recursion can seriously improve your coding efficiency! See the code section at the bottom of this page for the actual script.

solution

Here’s one solution – there are 92 in all

 

Problem 2 – The Knight’s Tour

This problem requires a bit more thinking about (well, not necessarily but we’ll get onto that). In this case, we have to move a single Knight around the chessboard, visiting each square once and only once. For the non-chess players here, a Knight moves in a sort of L shaped pattern like this:

knight moves

This Knight can move to any of the 8 squares shown

There are variations of this problem (for example having to return to the starting square or to make a symmetrical pattern) but we’ll just focus on the basic variation here where we must visit each square once and only once.

 

Backtracking Algorithm

This isn’t the most elegant solution but it works and it’s really intuitive which is why I came up with it. When I say ‘came up with’, a backtracking algorithm is a pretty standard way of solving this type of problem so it’s not like I invented anything here. Here is what I did:

  1. From the current square, look at all the squares to which a valid move is possible.
  2. Pick the square which will have the most valid moves from it and move to it. A valid move is a square that has not already been visited.
  3. Repeat the above.
    1. If none of the moves are valid, backtrack to the previous square and move to the square with the second highest number of valid moves.

So, a really simple algorithm. It works in most cases and is really quick. Here’s one of the solutions it gave:

solution on board

A Knight’s tour. There are many possible solutions and this is just one.

But why stop at an 8X8 grid? How about a 100 X 100 grid, or a 200 X 200 grid?

100 board image

A solution for a 100X100 grid. It’s interesting looking at some of the structures in this graph. It’s as if there are some highly ordered zones, while most of the board is more chaotic. It even looks like there are different ‘classes’ of ordered zones.

 

200 board image

A 200×200 grid. At this resolution we can only see the general pattern. However, we see similar structures to the 100×100 grid. I think it looks a bit like cells under a microscope…who knows, maybe there’s a link between how natural systems arrange themselves and avoiding previously occupied zones; as in the original problem (probably not but I like to use my imagination sometimes).

Pretty cool, but if I were doing this problem now I’d have done it completely differently.

 

Optimisation algorithms

Although the backtracking algorithm is simple, it still required me to think. And it doesn’t always work, you do sometimes need to re-run it to find a valid solution. Why not just offload all the thinking to the computer?

I’ve demonstrated genetic algorithms before. It would be easy to write such an algorithm to repeatedly try attempts at this problem until a valid solution was found. In fact, loads of machine learning algorithms could be used to solve the Knight’s Tour. A neural network would easily do it; using a node for each valid move or something like that. Or, a decision tree (or ensemble of them) could be constructed with each node representing a move.

I suppose I should write a script to do just that. I’ll post it on here if I get round to it. Or, if any readers are up for the challenge, feel free to post solutions in the comments.

 

Code

 

Script for the 8 queens problem. The first line can be changed to seek solutions for a board of any size. Some sizes have no possible solutions:

https://www.dropbox.com/s/yt0hb8wmfjzhxss/8q%20Solution.py?dl=0

 

Script for the Knight’s tour. As above, the first line may be changed to give solutions for a board of any size (note, running time increases proportional to the square of the board size). You can also pick any starting square:

https://www.dropbox.com/s/sro0d4cktaxt2p4/kt%20solution.py?dl=0

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s