The N-Queens Problem

The N-Queens Problem goes as follows: In a NxN square chess board, place all the queens so that they cannot kill each other – technically, it means no two queens can be in the same row/column/diagonal. As they say, part of the problem is solved by properly (mathematically or otherwise) phrasing the problem.

What does it mean to say the two queens are in the same row/column/diagonal? If we take $latex (r1, r2 .. r8)$ to be the row numbers of the queen for the columns 1 to 8, then for any i,j such that i is not equal to j, then if ri not equal to rj, it means that the two queens in question are not in the same column and same row. But how to make sure they are not in the same diagonal? Note that (ri, i) represents the co-ordinate for a queen on the chessboard. Two queens are in the same diagonal if one of the following is true: ri + i = rj + j or rii = rj – j. I took a 3×3 square and worked out to understand this.

Once these conditions are met, then it is more or less straight forward to do the actual check – loop over all values of column and row – if there is any failure, backtrack and start fresh with new values. Backtracking is one of the most elegant (may not be efficient) solutions to this problem.

A slightly related problem is detecting cycles in a di-graph (or a simple graph for that matter): This again takes a node, puts it in the list and tries to find its neighbors and adds them to the list, when it sees any neighbor (to be added) as the initial node, there is a cycle and it is noted. I will shortly come up with code for both of these problems.

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