## Introduction

The "eight queens problem" is a very old logical teaser. I think the original question is as old as chess game. The "modern" version of this problem is to solve this problem with help of computers.

This is a typical program writing competition task - like as towers of Hanoi. The challenge is to place eight queens on a chessboard, no to capture each other. And there are two questions:

- How to resolve it?
- How many solutions are there?

The siplest way to write a "bruteforce" program. Try each variaton and mark the good positions. But this is not a nice soultion. It would be very slow, because there are a very great number of positions.

The number of combinations is "8 under 64". That means (8! * (64-8)!) under 64! . (! sign means factorial) This is the formula of combinations without repetitions. If I calculated good - that means 4426165368 positions, what is too much to try each one. I found a shortest way to calculate, and demonstrate it in this solution.

Afterall this is a very good, and not too difficult example how to make a matematical model of a real (seems to be not matematical) problem. At last, I have to declare, this example is completely my work - I do not use any other sources (except queens picture in gif, what I found somewhere). Certainly everybody can find other solutions on Internet.

## Background

From perspective of C# programing, there are only two "interesting" or not "general" thing in this solution. I show ho can we store pictures (png) in the Program Resource and how can we use it, and the second is how can we create Form controls in runtime (pictureboxes in this case). In the first (or zero-th) step I draw four pngs: black, white, black-with-queen and white-with-queen fields. I used MSpaint and downloaded queens transparent png from the Internet.

## Using the code - the solution

The first observation was that every row, and every column of chessboard can contain one, and only one queen. The idea came from here. I gave numbers to each field, started with 0. Every fields have got an unique identifier. Every queen captures (prohibits) her row, her column, and two diagonals. Afterall the algoritm is not too difficult. In a loop program moves the first queen every fields of first row, and calculates the possible positions considering that EVERY rows, and columns can contain one and only one queen. First task was to calculate the fields, what the queen prohibits, then calculate tasks with second, with third etc.. queens, and make the summative array of prohibited fileds. Look at the picture below:

The queen on field 4 prohibits this fields: row: 0-7, column: 4,12,20, 28,36,44,52,60 left diagonal: 4,11,18,25,32, right diagonal :4,18,22,31. The program placed the first queen, than calculated the prohibited fields.

After then, the program calculated the POSSIBLE fields in second row: 8,9,10,14,15. In this picture I show an iteration, where program put the second queen on field 14, and calculated the summative prohibited fields (yellow and orange lines)

The summative means the sum of two prohibited field arrays. So the algorthm is that: Iterate on each field of FIRST row, place a queen into a field , calculate the prohibited fields, calculate the next row's possible fields. Then iterate on second row POSSIBLE fields, calculate the summative prohibited fields...etc and do it to egihth row. When iteration progress calculates that no fields are available in next row, then skips this position - moves the queen the next possible field.

To calcualte the fields I used eight nested loop the means the rows of chessboard. When iteration reaches the egihth row, and can place the eighth queen on a field that means it is a SOLUTION. A solution is an array of integers that contains the numbers of fields of queens. And ALL solutions is a List of this arrays. So I made a composite data sturcture:

List (int[]) solutions = new List(int[])()

This calculation takes place in `Form_load()`

method, so the calculation of possible positions is the first step in the program.

Calculating the prohibited fields...

The "`getdenied(item, denied)`

" method makes this calculation. The `item`

means the number of field which we are looking for, and `denied`

is a list of numbers of prohibited fields. The result will be the sum of this list, and the recently calculated list. Lets see the code:

List<int> t = new List<int>();
if (denied != null)
{
t.AddRange(denied);
}
....
row = item / 8;
column = item % 8;
rowmin = row * 8;
rowmax = rowmin + 7;
columnmin = column;
columnmax = column + 56;
leftdiagonalmin = item - Math.Min(row, column) * 9;
leftdiagonalmax = item + Math.Min(7 - row, 7 - column) * 9;
rightdiagonalmin = item - Math.Min(row, 7 - column) * 7;
rightdiagonalmax = item + Math.Min(7 - row, column) * 7;
for (int i = rowmin; i <= rowmax; i++)
{
t.Add(i);
}
for (int i = columnmin; i <= columnmax; i = i + 8)
{
t.Add(i);
}
for (int i = leftdiagonalmin; i <= leftdiagonalmax; i = i + 9)
{
t.Add(i);
}
for (int i = rightdiagonalmin; i <= rightdiagonalmax; i = i + 7)
{
t.Add(i);
}
List<int> tt = new List<int>();
tt = t.Distinct().ToList();
return tt;
...

...and after that to calculate the next row is very easy...

It makes the " `getrowsitems(row, denied);`

" method. `Row`

is the actual row, and `denied`

is a list of prohibited fields. This is not more than to filter the possible fields of next row which are NOT in prohibited fields list.

rowmin = row * 8;
rowmax = rowmin + 7;
if (denied != null)
{
for (int i = rowmin; i <= rowmax; i++)
{
if (!denied.Contains(i))
{
t.Add(i);
}
}
}
else
{
for (int i = rowmin; i <= rowmax; i++)
{
t.Add(i);
}
}
return t;
...

After the calculations the program draws the chessboard with "`InitializeBoard()`

" method This is an example how to create controls on a form, and gets pictures fro Program Resource. To change the black and white fields is a little bit tricky - see in my code. (not after ALL fileds have to change the color, after last field of a row the color will NOT change) And program initializes the numeric updown control with the number of solutions -nothing special.

bool blackwhite = false;
for (int y = 0; y <= 7; y++)
{
for (int x = 0; x <= 7; x++)
{
PictureBox pb = new PictureBox();
pb.SizeMode = PictureBoxSizeMode.StretchImage;
pb.Height = 70;
pb.Width = 70;
pb.Top = 1 + y * 70;
pb.Left = 1 + x * 70;
if (blackwhite)
{
pb.Image = (Image)Resources.ResourceManager.GetObject("black");
}
else
{
pb.Image = (Image)Resources.ResourceManager.GetObject("white");
}
panel1.Controls.Add(pb);
blackwhite = !blackwhite;
}
blackwhite = !blackwhite;
}
...

At last, let's see the updown control's value-change event. This method will change the fields pictures (picturebox components image property) according to the number of updown control - that means the index of solution. The pictureboxes are created (created in `Initializeboard`

method) so this method only changes the images. The images are in Program Resource as well.

...
bool blackwhite = false;
int[] solution_item = new int[8];
int idx = Convert.ToInt32(numericUpDown1.Value);
solution_item = solutions[idx - 1];
List<int> solution_item_list = solution_item.ToList();
List<Control> pbcontrollist = new List<Control>();
Image blackqueen = (Image)Resources.ResourceManager.GetObject("blackqueen");
Image whitequeen = (Image)Resources.ResourceManager.GetObject("whitequeen");
Image black = (Image)Resources.ResourceManager.GetObject("black");
Image white = (Image)Resources.ResourceManager.GetObject("white");
for (int ix = panel1.Controls.Count - 1; ix >= 0; ix--)
{
if (panel1.Controls[ix] is PictureBox) { pbcontrollist.Add(panel1.Controls[ix]); }
}
for (int i = 0; i < 64; i++)
{
if (solution_item_list.Contains(i))
{
if (blackwhite)
{
(pbcontrollist[i] as PictureBox).Image = blackqueen;
}
else
{
(pbcontrollist[i] as PictureBox).Image = whitequeen;
}
}
else
{
if (blackwhite)
{
(pbcontrollist[i] as PictureBox).Image = black;
}
else
{
(pbcontrollist[i] as PictureBox).Image = white;
}
}
int f = i / 8;
if (i != (7 + 8 * f))
{
blackwhite = !blackwhite;
}
}
}
blackwhite = !blackwhite;
}
...
...

## Points of Interest

This task is an "old debt" for me... I wanted to solve this problem from many years. I dont think so this would be a "large scale" problem. It is only a fun - but interesting and instructive. Worth to see and understand.

## History

This is the first (and maybe the last) version.