The problem of N queens. Solution using C++

The problem of N queens. Solution using C++


Contents



Introduction

In programming contests, the task of placing 8 Queens on a chessboard is often encountered: you need to write an algorithm in which 8 Queens are placed on a chessboard (size 8×8) in such a way that they do not beat each other. The simplest solution to this problem is the implementation of a complete search for all possible options for 8 nested loops with appropriate checks for intersection diagonally and vertically. But this option is not suitable for a task in which the number of queens is N, and the size of the board is N×N.

This topic describes the step-by-step process of developing an application that implements the classical task of placing N queens on a N×N board so that they do not beat each other. The paper proposes an iterative algorithm that solves this problem for any N. The algorithm of this example can be used in our own developments to solve problems of a combinatoric nature, in which you need to implement a complete search for all possible options to find all possible solutions.

 

Task

An integer N (N>0) is specified, which determines the number of queens on the board of size N×N. Develop a program that finds all possible placement options for N queens so that they do not “beat” each other. In the program you need to ensure the visualization of each received option.

The task is implemented as an application of type Windows Forms Application in C++ programming language.

 

Considerations

For an application like Visual C ++ – Windows Forms, Microsoft Visual Studio provides the appropriate controls for easy visualization of the received placement options.

A control of the DataGridView type is well suited for visualizing whiteboard N×N size. In this control, you can display data from both the database and directly in the form of a two-dimensional table.

The list of obtained variants in the form of coordinates (x1, y1), (x2, y2), …, (xN, yN) can be saved in the ListBox control, which is a dynamic list of arbitrary size.

When you select an option in the ListBox, the placement in the DataGridView will automatically be displayed.

 

Instructions

1. Features of the implementation of the algorithm for solving the task

1.1. Using an additional array to describe the placement of queens on the board

In the task, it is important to organize the data structures in such a way as to ensure the convenience of obtaining all possible variants of placing queens on the board.

To ensure complete enumeration of options, an additional one-dimensional array M of dimensionality N+1 is used in the work. The array element with index 0 (M[0]) is not used to provide convenience when operating with array indices.

In the array M, the coordinates of the placed queens are formed according to the following principle:

  • the x coordinate of the queen with the number k (k = 1..N) corresponds to the value M[k];
  • the y coordinate of the queen with the number k (k = 1..N) corresponds to the value k itself.

Figure 1 schematically shows the layout for N=5 on a 5 × 5 board and the array M

Placement of 5 Queens. C++ implementation

Figure 1. Interpretation of the values of the elements of the array M for a board of 5×5

As can be seen from the figure, the indices of the array M correspond to the y coordinate of the board, and the value M[i] at this index corresponds to the x coordinate of the board:

M[1] => x coordinate of the 1-st queen: (x1, y1) => (M[1], 1)
M[2] => x coordinate of the 2-nd queen: (x2, y2) => (M[2], 2)
...
M[k] => x coordinate of the k-th queen: (xk, yk) => (M[k], k)
...
M[N] => x coordinate of the N-th queen: (x, y) => (M[N], N)

The array M replaces the exhaustive search, which can be formed using N nested loops.

 

1.2. Algorithm description

The whole work of the algorithm is based on the formation of some placement of queens using the array M. The queen number that is placed is stored in some pointer variable, for example, with the name p. Depending on the situation, the pointer p moves to the right (p++) or left (p–) as shown in Figure 2 for 5 queens. So, the pointer p determines the number of the queen, which is located and the coordinate y. The value M[p] determines the x coordinate of the placed queen with the number p.

When the pointer value changes, the condition p=N is constantly checked, which means that the last queen is placed. If p=N and there are no overlaps between queens in the current placement, then this placement is fixed. In our case, the placement is fixed in the ListBox list as a special format string. If p<N, then the following changes of the pointer p (the number of the placed queen) or M[p] are determined depending on whether there is an overlay for the current number of queens and their placement.

The condition for the end of the iterative process is getting all possible options. In this case, the pointer p moves to the left to the element that follows before the first, that is, to the zero element.

Figure 2 shows different variants (states) of the array M based on the pointer p for N = 5. In the array M you can distinguish the following states:

  • 1 – initial state. This is the state of the array M, at which the iteration process begins;
  • 2 – intermediate state. This is some intermediate placement, when not all queens are placed and the k-th queen is placed (k = 1..N);
  • 3 – the placement option. It is a variant of the array M in which the desired placement is formed (the case when all N queens do not beat each other);
  • 4 – the end of the iterative process (p=0). The iterative process is completed if, after going through all the possible options, the pointer p moves to the left (p–) and becomes equal to 0.

Placement of N Queens. Algorithm description

Figure 2. Array M and its states during the formation of placement using the pointer p: 1) the initial state; 2) intermediate state; 3) the desired placement; 4) condition for the end of the iterative process

 

2. Program development

2.1. Start Microsoft Visual Studio. Create a project using a Windows Forms Application – C++ template

Start the Microsoft Visual Studio system (any version) and save the project. A detailed example of creating a project using a Windows Forms Application template can be viewed here.

The project name can be set arbitrary, for example, PlacementNQueens. As a result, an empty project form will be created.

 

2.2. Designing a Form of application
2.2.1. Placement of controls on the form

From the ToolBox panel, place the following controls on the form:

  • four Label controls to display informational messages. As a result, three instances (objects) of the Label type will be created that have the names label1, label2, label3, label4. One of these controls will display the number of placement options;
  • one control of type TextBox. An instance (object) is created with the name textBox1;
  • one control of type Listbox. An instance is created with the name listBox1;
  • one control of type DataGridView. An instance is created with the name dataGridView1. This control will display the board as a table;
  • one control of type Button. An instance named button1 is created. This control will run the placement search process for a given N.

Figure 3 shows the main form after placing the controls.

C++. Windows Forms template. Main form

Figure 3. The form of application after placing controls

 

2.2.2. Customize form controls

At this stage, you need to configure the following properties of controls:

  • in the control label1 property Text = “N = “;
  • in label2 property Text = “Placements”;
  • in label3 property Text = “Current placement”;
  • in label4 property Text = “Number of placements = “;
  • in button1 property Text = “Start”;
  • in Form1 property Text = “Placement of N Queens”.

After configuring the controls and configuring their size, the shape of the application will have an approximate appearance as shown in Figure 4.

C++. Windows Forms template. Main form

Figure 4. The form of application after configuring

 

3. Writing the code

3.1. Text of Form1.h module

When building the project, the entire program code will be typed from the module Form1.h. At the moment, the text of the form module is as follows:

#pragma once

namespace PlacementNQueens1 {
  using namespace System;
  using namespace System::ComponentModel;
  using namespace System::Collections;
  using namespace System::Windows::Forms;
  using namespace System::Data;
  using namespace System::Drawing;

  /// <summary>
  /// Summary for Form1
  /// </summary>
  public ref class Form1 : public System::Windows::Forms::Form
  {
  public:
    Form1(void)
    {
      InitializeComponent();
      //
      //TODO: Add the constructor code here
      //
    }

  protected:
    /// <summary>
    /// Clean up any resources being used.
    /// </summary>
    ~Form1()
    {
        if (components)
        {
          delete components;
    }
  }

  private: System::Windows::Forms::DataGridView^   dataGridView1;
  protected:
  private: System::Windows::Forms::Button^   button1;
  private: System::Windows::Forms::Label^ label1;
  private: System::Windows::Forms::ListBox^ listBox1;
  private: System::Windows::Forms::TextBox^   textBox1;
  private: System::Windows::Forms::Label^ label2;
  private: System::Windows::Forms::Label^ label3;
  private: System::Windows::Forms::Label^ label4;

  private:
    /// <summary>
    /// Required designer variable.
    /// </summary>
    System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code
    /// <summary>
    /// Required method for Designer support - do not modify
    /// the contents of this method with the code editor.
    /// </summary>

    void InitializeComponent(void)
    {
      this->dataGridView1 = (gcnew System::Windows::Forms::DataGridView());
      this->button1 = (gcnew System::Windows::Forms::Button());
      this->label1 = (gcnew System::Windows::Forms::Label());
      this->listBox1 = (gcnew System::Windows::Forms::ListBox());
      this->textBox1 = (gcnew System::Windows::Forms::TextBox());
      this->label2 = (gcnew System::Windows::Forms::Label());
      this->label3 = (gcnew System::Windows::Forms::Label());
      this->label4 = (gcnew System::Windows::Forms::Label());
      (cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->BeginInit();
      this->SuspendLayout();
      //
      // dataGridView1
      //
      this->dataGridView1->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;
      this->dataGridView1->Location = System::Drawing::Point(212, 60);
      this->dataGridView1->Name = L"dataGridView1";
      this->dataGridView1->Size = System::Drawing::Size(350, 290);
      this->dataGridView1->TabIndex = 0;
      //
      // button1
      //
      this->button1->Location = System::Drawing::Point(212, 10);
      this->button1->Name = L"button1";
      this->button1->Size = System::Drawing::Size(168, 23);
      this->button1->TabIndex = 1;
      this->button1->Text = L"Start";
      this->button1->UseVisualStyleBackColor = true;
      this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click);
      //
      // label1
      //
      this->label1->AutoSize = true;
      this->label1->Location = System::Drawing::Point(12, 15);
      this->label1->Name = L"label1";
      this->label1->Size = System::Drawing::Size(27, 13);
      this->label1->TabIndex = 2;
      this->label1->Text = L"N = ";
      //
      // listBox1
      //
      this->listBox1->FormattingEnabled = true;
      this->listBox1->Location = System::Drawing::Point(15, 60);
      this->listBox1->Name = L"listBox1";
      this->listBox1->Size = System::Drawing::Size(194, 290);
      this->listBox1->TabIndex = 3;
      this->listBox1->Click += gcnew System::EventHandler(this, &Form1::listBox1_Click);
      this->listBox1->KeyUp += gcnew System::Windows::Forms::KeyEventHandler(this, &Form1::listBox1_KeyUp);
      //
      // textBox1
      //
      this->textBox1->Location = System::Drawing::Point(63, 12);
      this->textBox1->Name = L"textBox1";
      this->textBox1->Size = System::Drawing::Size(100, 20);
      this->textBox1->TabIndex = 4;
      //
      // label2
      //
      this->label2->AutoSize = true;
      this->label2->Location = System::Drawing::Point(12, 44);
      this->label2->Name = L"label2";
      this->label2->Size = System::Drawing::Size(62, 13);
      this->label2->TabIndex = 5;
      this->label2->Text = L"Placements";
      //
      // label3
      //
      this->label3->AutoSize = true;
      this->label3->Location = System::Drawing::Point(209, 44);
      this->label3->Name = L"label3";
      this->label3->Size = System::Drawing::Size(93, 13);
      this->label3->TabIndex = 6;
      this->label3->Text = L"Current placement";
      //
      // label4
      //
      this->label4->AutoSize = true;
      this->label4->Location = System::Drawing::Point(12, 362);
      this->label4->Name = L"label4";
      this->label4->Size = System::Drawing::Size(125, 13);
      this->label4->TabIndex = 7;
      this->label4->Text = L"Number of placements = ";
      //
      // Form1
      //
      this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);
      this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;
      this->ClientSize = System::Drawing::Size(730, 395);
      this->Controls->Add(this->label4);
      this->Controls->Add(this->label3);
      this->Controls->Add(this->label2);
      this->Controls->Add(this->textBox1);
      this->Controls->Add(this->listBox1);
      this->Controls->Add(this->label1);
      this->Controls->Add(this->button1);
      this->Controls->Add(this->dataGridView1);
      this->Name = L"Form1";
      this->Text = L"Placement of N Queens";
      (cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->EndInit();
      this->ResumeLayout(false);
      this->PerformLayout();
    }
#pragma endregion
  }
}

 

3.2. Declaring the internal variable N (number of queens)

An internal hidden variable N is entered in the class text, which determines the number of queens to be placed and the size of the board.

private:
    int N; // number of queens

After entering N, the class of Form1 form is as follows:

...
public ref class Form1 : public System::Windows::Forms::Form
{
private:
    int N; // number of queens

public:
    Form1(void)
    {
        InitializeComponent();
        //
        //TODO: Add the constructor code here
        //
    }

...

}
...

 

3.3. The IsStrike() method. The check whether two queens are beating at different coordinates.

The IsStrike() method is introduced into the text of the Form1 class. The method checks whether two queens are “beating” with different coordinates. The method gets 4 integer parameters:

  • x1, y1 – coordinates of the first queen;
  • x2, y2 – coordinates of the second queen.

The method returns true if two queens “beat” each other. The method checks both horizontally and vertically.

The method must be placed in the Form1 class after the directive

#pragma endregion


The method code in the Form1 class is as follows

...

public ref class Form1 : public System::Windows::Forms::Form
{
    ...

#pragma endregion

    // Checking if 2 queens are beating. It returns false if they are not beating
    bool IsStrike(int x1, int y1, int x2, int y2)
    {
        // 1. Horizontal, vertical
        // Queens beat each other if the corresponding 2 parameters match
        if ((x1 == x2) || (y1 == y2)) return true;

        // 2. Main diagonal
        int tx, ty; // additional variables

        // 2.1. Left-Up
        tx = x1 - 1; ty = y1 - 1;
        while ((tx >= 1) && (ty >= 1))
        {
            if ((tx == x2) && (ty == y2)) return true;
            tx--; ty--;
        }

        // 2.2. Right-Down
        tx = x1 + 1; ty = y1 + 1;
        while ((tx <= N) && (ty <= N))
        {
            if ((tx == x2) && (ty == y2)) return true;
            tx++; ty++;
        }

        // 3. Additional diagonal
        // 3.1. Right-Up
        tx = x1 + 1; ty = y1 - 1;
        while ((tx <= N) && (ty >= 1))
        {
            if ((tx == x2) && (ty == y2)) return true;
            tx++; ty--;
        }

        // 3.2. Left-Down
        tx = x1 - 1; ty = y1 + 1;
        while ((tx >= 1) && (ty <= N))
        {
            if ((tx == x2) && (ty == y2)) return true;
            tx--; ty++;
        }
        return false;
    }
};

...

 

3.4. Method Strike(). Check of placed queen overlap with previous (already placed) queens

The Strike() method is designed to check the coordinates of a queen, which is placed with the coordinates of previously placed queens who do not beat each other.

The method receives as input parameters an array M and a pointer p (see sections 1.2-1.3). The array M contains information about:

  • queen coordinates that are considered to be placed and not superimposed;
  • pointer p representing the number of the queen being placed. Hence, the coordinate M[p] is the x coordinate of the current queen, which is located. The coordinate p is the y coordinate of the current queen, which is located.

The method checks whether the queen beats with coordinates that correspond to the position p, with queens that are placed in positions 1, 2, …, p-1.

The method must be placed in the Form1 class after the IsStrike() method. The method code in the Form1 class is as follows:

// Checking whether the last element M [p]is superimposed
// with elements M[1], M[2], ..., M[p-1].
// This function uses the IsStrike() function.
bool Strike(int M[], int p)
{
    int px, py, x, y;
    int i;

    px = M[p];
    py = p;

    for (i = 1; i <= p - 1; i++)
    {
        x = M[i];
        y = i;
        if (IsStrike(x, y, px, py))
            return true;
    }
    return false;
}

 

3.5. Methods to display the placement of queens in dataGridView1
3.5.1. InitDataGridView() method. Initialization and customization of the dataGridView1 control

The dataGridView1 control is used to display the location recorded in listBox1. The InitDataGridView() method implements the initial initialization of dataGridView1 programmatically. The method takes the input parameter value N.

The method must be placed after the Strike() method. The listing of the InitDataGridView() method in the Form1 class is as follows

// dataGridView1 initialization
// N - number of Queens
void InitDataGridView(int N)
{
    int i;

    dataGridView1->Columns->Clear();

    // form the dataGridView1 - add columns
    for (i = 1; i <= N; i++)
    {
        dataGridView1->Columns->Add("i" + i.ToString(), i.ToString());

        // column width in pixels
        dataGridView1->Columns[i - 1]->Width = 30;
    }

    // add rows
    dataGridView1->Rows->Add(N);

    // display row numbers
    for (i=1; i<=N; i++)
        dataGridView1->Rows[i-1]->HeaderCell->Value = i.ToString();

    // pick up the last row so that no rows can be added in run mode
    dataGridView1->AllowUserToAddRows = false;

    // center alignment in all rows
    dataGridView1->RowsDefaultCellStyle->Alignment = DataGridViewContentAlignment::MiddleCenter;
}

 

3.5.2. Display a string from listBox1 in dataGridView1. ShowDataGridView() method

The listBox1 control displays rows that contain variants of the resulting placements. Strings are formed in their own format. The selected row in listBox1 is displayed in dataGridView1 as a matrix (chessboard).

The ShowDataGridView() method is designed to process the selected row in listBox1 and visualize the coordinates of the queens represented in this row. The queens coordinates formed as a string are visualized in dataGridView1.

The method receives as input parameters:

  • string s, in which pairs of queens coordinates are placed for received placements;
  • number of Queens N.

The text of the method is placed after the InitDataGridView() method.

The program code of the ShowDataGridView() method in the Form1 class is as follows

// a method that displays the string s in dataGridView1,
// N - number of Queens
// accept that dataGridView1 is already initialized to size N * N
void ShowDataGridView(String ^ s, int N)
{
    int i;
    int j;
    String ^ xs;
    String ^ ys;
    int x, y;

    // first clear the dataGridView1
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            dataGridView1->Rows[i]->Cells[j]->Value = "";

    j = 0; // offset
    for (i = 0; i < N; i++)
    {
        // form xs
        xs = "";
        while (s[j] != ',')
        {
            xs = xs + s[j].ToString();
            j++;
        } // xs - number x as a string

        // scroll offset
        j++;

        // form ys
        ys = "";
        while (s[j] != '-')
        {
            ys = ys + s[j].ToString();
            j++;
        }

        // scroll offset
        j++;

        // converting: xs->x, ys->y
        x = x.Parse(xs);
        y = y.Parse(ys);

        // designate a position x, y of a Queen
        dataGridView1->Rows[y - 1]->Cells[x - 1]->Value = "X";
    }
}

 

3.6. Methods of work with listBox1
3.6.1. Add placements to listBox1 in string format. AddToListBox() method

The AddToListBox() method performs the following operations:

  • converts the placement described in the rows of the array M to a string of type string;
  • adds the generated string to the list in listBox1.

An example of string s of type string for N=5 and the array M shown in Figure 1:

"11-23-35-42-54-"

The text of the method is placed after the ShowDataGridView() method. The program code of the AddToListBox() method in the text of Form1 is as follows:

// write string to listBox1
void AddToListBox(int M[], int N)
{
    // add string to listBox1
    String ^ s;
    for (int i = 1; i <= N; i++)
        s = s + M[i].ToString() + "," + i.ToString() + "-";
    listBox1->Items->Add(s);
}

 

3.6.2. Programming the Click and KeyUp event handlers of the listBox1 control

In the listBox1 control, a list of strings is formed that correspond to the received placements of N queens on the board of N×N size. In the program, you need to provide a visualization in the dataGridView1 of the row selected in the listBox1. In order for the user to conveniently review the received placements in the dataGridView1, you need to program the Click and KeyUp event handlers of the listBox1 control.

This topic does not cover the detailed process of programming the Click and KeyUp event handlers, since it is implemented in the standard way. A more detailed example of how an event handler is programmed in Microsoft Visual Studio is described in the topic:

Event handlers are placed after the AddToListBox() method. The program code of the event handlers Click and KeyUp for the listBox1 control is as follows:

// click on listBox1
private: System::Void listBox1_Click(System::Object^   sender, System::EventArgs^ e) {
    if (listBox1->Items->Count <= 0) return;
    int num;
    num = listBox1->SelectedIndex;
    ShowDataGridView(listBox1->Items[num]->ToString(), N);
}

// key pressed in listBox1 - KeyUp event
private: System::Void listBox1_KeyUp(System::Object^   sender, System::Windows::Forms::KeyEventArgs^ e) {
    if (listBox1->Items->Count <= 0) return;
    int num;
    num = listBox1->SelectedIndex;
    ShowDataGridView(listBox1->Items[num]->ToString(), N);
}

 

3.7. Programming the Click event on the Start button. Algorithm of searching of elements placements

When you press the Start key, the user must obtain a list of placements of N queens. All this is done in the Click event handler, which is called when the Start button is clicked.

The event handler implements an algorithm, which is described in Section 1.3.

The program code of event handler is as follows:

// Click event handler on a Button control - implements placement
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
    const int MaxN = 20;
    int M[MaxN];
    int p; // queen number
    int k; // number of placement options

    // get the number of queens
    N = N.Parse(textBox1->Text);

    // Initialize dataGridView1
    InitDataGridView(N);

    // clear listBox1
    listBox1->Items->Clear();

    // THE ALGORITHM FOR GENERATING PLACEMENTS
    // initial settings
    p = 1;
    M[p] = 0;
    M[0] = 0;
    k = 0;

    // the cycle of placements search
    while (p > 0) // if p==0, then exit from the loop
    {
        M[p] = M[p] + 1;
        if (p == N) // last item
        {
            if (M[p] > N)
            {
                while (M[p] > N) p--; // rewind
            }
            else
            {
                if (!Strike(M, p))
                {
                    // fix placement
                    AddToListBox(M, N);
                    k++;
                    p--;
                }
            }
        }
        else // not the last item
        {
            if (M[p] > N)
            {
                while (M[p] > N) p--; // rewind
            }
            else
            {
                if (!Strike(M, p)) // If M[p] does not overlap with previous M[1], M[2], ..., M[p-1]
                {
                    p++; // go to the placement of the next queen
                    M[p] = 0;
                }
            }
        }
    }

    // display the number of placement options
    if (k > 0)
    {
        listBox1->SelectedIndex = 0;
        listBox1_Click(sender, e);
        label4->Text = " Number of placements = " + k.ToString();
    }
}

 

3.8. Summary of program code

The program has an internal variable N (the number of queens and the size of the board).

The program (in Form1 class) implements the following methods:

  • IsStrike() method – checks if two coordinates are “beating” diagonally and vertically;
  • Strike() method – checks if a given queen beats with pre-placed queens;
  • InitDataGridView() method – performs initialization of the dataGridView1 control depending on the value of N;
  • method ShowDataGridView() – displays the described placement from the input string s in dataGridView1;
  • AddToListBox() method – converts the placement from array M to a string of special format s and adds this string to the listBox1 list;
  • two methods are the event handlers listBox1_Click() and listBox1_KeyUp(), which allow you to conveniently revise placements when the selected row changes to listBox1;
  • event handler button1_Click() of click on the Start button – implements the basic placement algorithm.

 

4. Run the program. Program testing

The result of the program is shown in Figure 5. You can set different values of N. If the value of N is set large enough (N>13), then you will have to wait a little for a solution :).

C++ program result number of queens N=7

Figure 5. The result of the program for the number of queens N=7. The number of placement options is 40