Courses/CS 461/Winter 2006/Chris Lemcke/Week 7

From CSWiki

< Courses | CS 461 | Winter 2006 | Chris Lemcke

1 The N-Queens Problem

[edit] The N-Queens Problem

The N-Queens problem is the classic mathematical problem of putting N chess queens on an NxN chessboard, where no queen is in the line of sight of another queen. That is, no queen is directly below or above another, directly to the right or the left of another, or in a diagonal from any other queen. This is trivial if there is one queen, and is impossible for two or three queens:

[edit] Two Queens

[edit] Three Queens

[edit] Multi-Agent Solutions for N-Queens

I have found a number of different systems for the N-queens problem. They all work in the same basic way:

Each queen is represented by a unique agent, one for each row. Then, each queen changes what column it is in until it recieves no more messages. Queens higher up have a higher priority, so they tend to move less. Queens recieve messages about the positions of other queens, and calculate whether any other queen of higher priority is in the same column or diagnol. How each queen calculates this is based on each specific algoritm. Some algorithms create a possible solution in less steps, but with significantly more messages being sent, others have most of the messages sent to a small number of agents, others are more spread out.

Here are a number of N-Queen netlogo models: