Eight Queens Problem

• Download EightQueens.zip - 50.1 KB

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:

            //Local list of integer
            List<int> t = new List<int>();

            //Adds prohibited list to t
            if (denied != null)
            {
                t.AddRange(denied);
            }
  
            ....
			
			
            //actual row is the item divided by 8 (INTEGER!!!)
            row = item / 8;

            //actual column is the item MODULO 8
            column = item % 8;

            //The actual row min is row *8
            rowmin = row * 8;
            //..and the max is min+7...
            rowmax = rowmin + 7;


            columnmin = column;
            //Colunmax is the columnmin+56 (7*8) (check if not belive....)
            columnmax = column + 56;

            //Left diagonal min and max...
            leftdiagonalmin = item - Math.Min(row, column) * 9;
            leftdiagonalmax = item + Math.Min(7 - row, 7 - column) * 9;

            //Right diagonal min and max
            rightdiagonalmin = item - Math.Min(row, 7 - column) * 7;
            rightdiagonalmax = item + Math.Min(7 - row, column) * 7;

            //Calculate the prohibited row fields from min to max, and adds to t (list)

            for (int i = rowmin; i <= rowmax; i++)
            {
                t.Add(i);
            }

            //Calculate the prohibited columns from min to max step by 8 and adds to t

            for (int i = columnmin; i <= columnmax; i = i + 8)
            {
                t.Add(i);
            }

            //Calculate the left diagonal from min to max step by 9 (8+1 same column and 1 field to right) 

            for (int i = leftdiagonalmin; i <= leftdiagonalmax; i = i + 9)
            {
                t.Add(i);
            }

            //Calculate to right diagonal from min to max step by 7 (8-1 same column and 1 field to left)

            for (int i = rightdiagonalmin; i <= rightdiagonalmax; i = i + 7)
            {
                t.Add(i);
            }

            //Calculate distinct : each fieldnumber can take part only one time. One field can be prohibited by more queens not only for one, but enough to mark this field only one 
            List<int> tt = new List<int>();

            tt = t.Distinct().ToList();
			
			//Returns the new prohibited array, the original, and the new added.
            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.

            //Calculate the actual row min, and max values
            rowmin = row * 8;
            rowmax = rowmin + 7;
         
            //If prohibited list is not null...
            if (denied != null)
            {

                //Loop through the row from min to max to each field
                for (int i = rowmin; i <= rowmax; i++)
                {
                    //If the prohibited list NOT contains the field index, then add to list (will be returned)
                    if (!denied.Contains(i))
                    {
                        t.Add(i);
                    }

                }
            }
            //If prohibited list doesn't contain elements, then whole row is available (it can be happen only FIRST row)
            else
            {
                //Adds whole row from min to max to available fields list.
                for (int i = rowmin; i <= rowmax; i++)
                {
                    t.Add(i);
                }
            }

            //REturns the available lists
            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.

            //Black or white fields? blackwhite true means BLACK!
            bool blackwhite = false;

            //Nested loops to draw the chessboards. Calculates the position of pictures. Each chessboard fields have 70*70 size
            for (int y = 0; y <= 7; y++)
            {
                for (int x = 0; x <= 7; x++)
                {

                    //Creates new Picturebox, sterched, with 70 pixel height and width
                    PictureBox pb = new PictureBox();
                    pb.SizeMode = PictureBoxSizeMode.StretchImage;
                    pb.Height = 70;
                    pb.Width = 70;


                    //Calculates the position 1, 71,141 etc. 
                    pb.Top = 1 + y * 70;
                    pb.Left = 1 + x * 70;


                    //If the field is black...then draw blac, else white
                    if (blackwhite)
                    {
                        //Gets the picture from Program Resource. Resource can contain OBJECT, so we have to explicitely convert to Image
                        pb.Image = (Image)Resources.ResourceManager.GetObject("black");
    
                    }
                    else
                    {
                        //Same if the field is white
                        pb.Image = (Image)Resources.ResourceManager.GetObject("white");
          
                    }

                    //Adds the new control (picturebox) to Panel1 component
                    panel1.Controls.Add(pb);

                    //Change the blaxk or white flag
                    blackwhite = !blackwhite;
                    
                }
                //.. and here too, because in the beginning of a new row will NOT change the color. The last field, and a next row first field have the same color!
                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.

             ...
			 //Occures when numeric we change the value of the updown controller

            //Black or white flag, true means BLACK!
            bool blackwhite = false;

            //Local array: the solutio is a list of array of integer. This is an item of solutions!
            int[] solution_item = new int[8];

            //numeric updown index. The value is DECIMAL so we convert it to int.
            int idx = Convert.ToInt32(numericUpDown1.Value);

            //The idx-th element of solutions list is the local solution item.
            solution_item = solutions[idx - 1];

            //Converts the list to array => because .Contains method is very comfortable. (see below)
            List<int> solution_item_list = solution_item.ToList();

            //List of form controls This will be a list of pictureboxes on Panel1
            List<Control> pbcontrollist = new List<Control>();

            //Captures four images from Program Resource. The resource can contain object, so we convert it to Image
            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");

            //Loop through the panel1 controls, and if it is picturebox, then adds to pbcontrollist
            for (int ix = panel1.Controls.Count - 1; ix >= 0; ix--)
            {
                if (panel1.Controls[ix] is PictureBox) { pbcontrollist.Add(panel1.Controls[ix]); }
            }

            //Loop through in all 64 fields of chessboard (0..63) and if local soution contains the number of field then draws a queen to chessboard. In other case it draws a simple field.
            //Of course it have to calculate to black or white color as well.
        
            for (int i = 0; i < 64; i++)
            {
                //If local solution contains the number then QUEEN!
                if (solution_item_list.Contains(i))
                {
                    //Black or White Queen?
                    if (blackwhite)
                    {
                        //pbcontrollist[i] is a Control type, not a Picturebox. So we have to convert to Picturebox with "AS" 
                        (pbcontrollist[i] as PictureBox).Image = blackqueen;
                    }
                    else
                    {
                        (pbcontrollist[i] as PictureBox).Image = whitequeen;
                    }
                }
                ////If local solution does not containsthe number then simple field!
                else
                {
                    if (blackwhite)
                    {
                        (pbcontrollist[i] as PictureBox).Image = black;
                    }
                    else
                    {
                        (pbcontrollist[i] as PictureBox).Image = white;
                    }
                }

                //Problem:  after the last field of a row will NOT change the color (see a chessboard) It calculates the last field. If i is NOT index of a last-row field, then changes the color (black-white)
                
                int f = i / 8;

                //Not last field of a row? Then change...else NOT.
                if (i != (7 + 8 * f))
                {
                    blackwhite = !blackwhite;
                }


            }

            }
                //.. and here too, because in the beginning of a new row will NOT change the color. The last field, and a next row first field have the same color!
                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.