The problem of N queens. Solution using Delphi

The problem of N queens. Solution using Delphi


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.

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 needs to be implemented in the Delphi programming system (any version) as an application like VCL Forms Application – Delphi.

 

Considerations

For applications such as VCL Forms Application,  Delphi system provides appropriate controls for easy visualization of the obtained placement options.

The TStringGrid component is great for visualizing chessboard N×N. In this component, 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 TListBox control, which is a dynamic list of arbitrary size.

When you select an option in the TListBox, the placement in the TStringGrid will automatically be displayed.

 

Instructions

1. Features of the implementation of the task solving algorithm

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 is used in the work. 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

Delphi Soving the problem of placing queens on a chessboard

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. Description of the algorithm

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 increases (p:=p+1) or decreases (p:=p-1) 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:=p-1) and becomes equal to 0.

Delphi Soving the problem of placing queens on a chessboard Data structures

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. Run Delphi. Create a project on the template VCL Forms Application – Delphi

Start the Delphi system (any version) and save the project. A detailed example of creating a project using the VCL Forms Application – Delphi template can be viewed here.

The project name can be set arbitrary, for example, Project1. 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 components on the form:

  • four TLabel type components for displaying informational messages. As a result, three instances (objects) of the TLabel type will be created, which have the names Label1, Label2, Label3, Label4. One of these components will display the number of placement options;
  • one component of TEdit type. An instance (object) is created with the name Edit1;
  • one component of TListBox type. An instance is created with the name ListBox1;
  • one component of TStringGrid type. An instance named StringGrid1 is created. This component will display placement on the board;
  • one component of type TButton. An instance named Button1 is created. This component will launch the process of searching for placements for a given N.

Figure 3 shows the application form after placing the components.

Delphi. VCL Forms Application. Main form

Figure 3. The form of application after placing components

 

2.2.2. Customize form components

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

  • in the component Label1 property Caption = “N =”;
  • in Label2 property Caption = “Placements”;
  • in Label3 property Caption = “Current placement”;
  • in Label4 property Caption = “Number of placements = “;
  • in Button1 property Caption = “Start”;
  • in the component Form1 property Caption = “Placement of N Queens”;
  • in Edit1 property Text =””.

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

Delphi. VCL Forms Application. Main form

Figure 4. The form of application after configuring

 

3. Writing the code

3.1. Text of Unit1.pas module

At the moment, the text of the module, which corresponds to the main form of the program, is as follows:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Grids, StdCtrls;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Edit1: TEdit;
    Button1: TButton;
    Label2: TLabel;
    ListBox1: TListBox;
    Label3: TLabel;
    StringGrid1: TStringGrid;
    Label4: TLabel;
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

end.

 

3.2. Declaring Variables, Constants, and Data Types

To make it easier to work with procedures and functions, the following should be entered into the class text:

  • the Max constant, which determines the maximum possible number of queens;
  • internal private variable N, which determines the current number of queens;
  • TArray type, which is required to pass an array of integers to a function as a parameter.

After the actions performed, the abbreviated code of the program will be as follows:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Grids, StdCtrls;

const
  Max = 20; // the maximum number of queens and the board size

type
  TArray = array [0..Max] of integer; // additional type - array

  TForm1 = class(TForm)
    Label1: TLabel;
    Edit1: TEdit;
    Button1: TButton;
    Label2: TLabel;
    ListBox1: TListBox;
    Label3: TLabel;
    StringGrid1: TStringGrid;
    Label4: TLabel;
  private
    { Private declarations }
    N:integer; // number of queens, board size
  public
    { Public declarations }
  end;

...

 

3.3. Functions Strike() and IsStrike().Check whether two queens are beating at different coordinates.

The Strike() and IsStrike() functions are introduced into the form class of the Unit1.pas module. The implementation section introduces the listings of the functions. Functions serve as the basis for checking the “beating” queens.

The IsStrike() function 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.

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

The Strike() function 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.

Function 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 Strike() function 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 program code of the Strike() and IsStrike() functions in the implementation section is as follows:

...

implementation

{$R *.dfm}

// Checking if 2 queens are beating. It returns false if they are not beating

function TForm1.IsStrike(x1, y1, x2, y2:integer):boolean;
var
  tx, ty:integer;
begin
  // 1. Horizontal, vertical
  // Queens beat each other if the corresponding 2 parameters match
  if (x1=x2) or (y1=y2) then
  begin
    IsStrike := true;
    exit;
  end;

  // 2. 2. Main diagonal
  // 2.1. Left-Up
  tx := x1-1;
  ty := y1-1;

  while (tx>=1)and(ty>=1) do
  begin
    if (tx=x2)and(ty=y2) then
    begin
      IsStrike:=true;
      exit;
    end;
    tx:=tx-1; ty:=ty-1;
  end;

  // 2.2. Right-Down
  tx:=x1+1; ty:=y1+1;
  while (tx<=N)and (ty<=N) do
  begin
    if (tx=x2) and (ty=y2) then
    begin
      IsStrike:=true;
      exit;
    end;
    tx:=tx+1;
    ty:=ty+1;
  end;

  // 3. Additional diagonal
  // 3.1. Right-Up
  tx:=x1+1; ty:=y1-1;
  while (tx<=N)and(ty>=1) do
  begin
    if (tx=x2)and(ty=y2) then
    begin
      IsStrike:=true;
      exit;
    end;
    tx:=tx+1;
    ty:=ty-1;
  end;

  // 3.2. Left-Down
  tx:=x1-1; ty:=y1+1;
  while (tx>=1)and(ty<=N) do
  begin
    if (tx=x2)and(ty=y2) then
    begin
      IsStrike:=true;
      exit;
    end;
    tx:=tx-1;
    ty:=ty+1;
  end;
  IsStrike:=false;
end;

function TForm1.Strike(M: TArray; p: Integer):boolean;
var
  px, py, x, y, i: integer;
begin
  px := M[p];
  py := p;

  for i:=1 to p-1 do
  begin
    x := M[i];
    y := i;
    if IsStrike(x,y,px,py) then
    begin
      Strike:=true;
      exit;
    end;
  end;
  Strike:=false;
end;

...

Previously in the class of Form1 must be described the signatures of functions

...
TForm1 = class(TForm)
  Label1: TLabel;
  Edit1: TEdit;
  Button1: TButton;
  Label2: TLabel;
  ListBox1: TListBox;
  Label3: TLabel;
  StringGrid1: TStringGrid;
  Label4: TLabel;
private
  { Private declarations }
  N:integer; // number of queens, board size
public
  { Public declarations }
  function IsStrike(x1, y1, x2, y2:integer):boolean;
  function Strike(M:TArray; p:integer):boolean;
end;
...

 

3.4. Procedures of placement displaying in StringGrid1

The StringGrid1 component is used to display the location saved in ListBox1. The StringGrid1 component is a two-dimensional string table that is conveniently configured and processed. The program for working with the StringGrid1 component uses two procedures: InitStringGrid() and ShowStringGrid().



 

3.4.1. Inclusion of signatures of procedures for working with the StringGrid1 component in the text of the TForm1 class

Before implementing the procedures for working with the StringGrid1 component, the following procedure signatures must be entered in the public (or private) section of the text of the TForm1 class

...
TForm1 = class(TForm)
...
private
  { Private declarations }
  N:integer; // number of Queens
public
  { Public declarations }
  ...
  // The procedures of TStringGrid processing
  procedure InitStringGrid(N:integer);
  procedure ShowStringGrid(s:string; N:integer);
end;
...

 

3.4.2. Initialization and configuring StringGrid1. Procedure InitStringGrid()

The InitStringGrid() procedure implements the initial initialization of a StringGrid1 programmatically. The procedure receives the input parameter value N.

The program code of the InitStringGrid() procedure in the Form1 class is as follows

...
// initialization of StringGrid
procedure TForm1.InitStringGrid(N: Integer);
var
  i,j:integer;
begin
  // board edges
  StringGrid1.FixedCols:=1;
  StringGrid1.FixedRows:=1;

  // board dimensions
  StringGrid1.RowCount:=N+1;
  StringGrid1.ColCount:=N+1;

  // header
  for i:=1 to N do
  begin
    StringGrid1.Cols[i].Text:=IntToStr(i);
    StringGrid1.Rows[i].Text:=IntToStr(i);

    // column width
    StringGrid1.ColWidths[i]:=30;
  end;

  // width of zero column
  StringGrid1.ColWidths[0]:=35;

  // cell clearing
  for i:=1 to N do
    for j:=1 to N do
      StringGrid1.Cells[i,j]:='';
end;
...

 

3.4.3. Display a string from listBox1 in StringGrid1. Procedure ShowStringGrid()

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 StringGrid1 as a matrix (chessboard).

The ShowDataGridView() procedure 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 StringGrid1.

The procedure receives as input parameters:

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

The listing of the ShowStringGrid() procedure in the implementation section is as follows

...
// A procedure that displays the string s in StringGrid1,
// N - number of Queens
// accept that dataGridView1 is already initialized to size N * N
procedure TForm1.ShowStringGrid(s: string; N: Integer);
var
  i, j:integer;
  xs, ys:string;
  x, y:integer;
begin
  // clear StringGrid1
  for i:=1 to N do
    for j:=1 to N do
      Form1.StringGrid1.Cells[i,j]:='';

  j:=0; // offset

  for i:=1 to N do
  begin
    // form xs
    xs:='';
    while s[j+1] <> ',' do
    begin
      xs:=xs+s[j+1];
      j:=j+1;
    end; // xs - number x as a string

    // scroll offset
    j:=j+1;

    // form ys
    ys:='';
    while s[j+1]<>'-' do
    begin
      ys:=ys+s[j+1];
      j:=j+1;
    end;

    // scroll through
    j:=j+1;

    x:=StrToInt(xs);
    y:=StrToInt(ys);

    // designate the position x, y of a queen
    StringGrid1.Cells[x,y]:='X';
  end;

end;
...

 

3.5. Programming the OnActivate form activation event

At this stage, the InitStringGrid() method call should be entered into the OnActivate event handler of the main Form1 program.

A detailed example of programming an event in the Delphi system is described in the topic:

Program code the main form’s OnActivate event handler is as follows

// Form's activation
procedure TForm1.FormActivate(Sender: TObject);
begin
  InitStringGrid(1);
end;

 

3.6. Procedures for working with ListBox1
3.6.1. Adding a placement in ListBox1 in string format. AddToListBox() procedure

The AddToListBox() procedure 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-"

Previously, in the text of the class TForm1 you need to enter the signature of the procedure AddToListBox():

TForm1 = class(TForm)
...
private
  { Private declarations }
  N:integer; // number of queens, board size
public
  { Public declarations }
  ...
  // add string s to ListBox1 in specified format
  procedure AddToListBox(M:TArray; N:integer);
end;

Program code of the AddToListBox() procedure in the implementation section is as follows:

...
// write string to listBox1
procedure TForm1.AddToListBox(M:TArray; N:integer);
var
  s:string;
  i:integer;
begin
  for i:=1 to N do
    s:=s+IntToStr(M[i])+','+IntToStr(i)+'-';
  ListBox1.Items.Add(s);
end;
...

 

3.6.2. Programming the Click event of the ListBox1 component

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.

The listBox1 component forms a list of strings that describe the resulting placement of N queens on the board of N×N size. In the program you need to provide a visualization in StringGrid1 of the selected row in ListBox1. In order for the user to conveniently revise the received placements in StringGrid1, you need to program the Click event handler of the listBox1 component.

A more detailed example of how an event handler is programmed in Delphi is described in the topic:

The program code of the Click event handler for the listBox1 component is as follows:

...
// clicking on a row in ListBox1
procedure TForm1.ListBox1Click(Sender: TObject);
var
  num:integer;
begin
  if ListBox1.Items.Count<=0 then
    exit;
  num:=ListBox1.ItemIndex;
  ShowStringGrid(ListBox1.Items[num],N);
end;
...

 

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
procedure TForm1.Button1Click(Sender: TObject);
var
  M:TArray; // array, forming the placement of queens
  p:integer; // queen number
  k:integer; // number of placement options
begin
  // get the number of queens
  N:=StrToInt(Edit1.Text);

  // Initialize StringGrid1
  InitStringGrid(N);

  // очистить listBox1
  ListBox1.Items.Clear;

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

  // the cycle of placements search
  while p>0 do
  begin
    M[p]:=M[p]+1;
    if p=N then // last item
    begin
      if M[p]>N then
        while M[p]>N do p:=p-1 // rewind
      else
      begin
        if not Strike(M,p) then
        begin
          // fix placement
          AddToListBox(M,N);
          k:=k+1;
          p:=p-1;
        end;
      end;
    end
    else // not the last item
    begin
      if M[p]>N then
        while M[p]>N do p:=p-1 // rewind
      else
      begin
        if not Strike(M,p) then
        begin
          p:=p+1;
          M[p]:=0;
        end;
      end;
    end;
  end;

  // display the number of placement options
  if k>0 then
  begin
    ListBox1.ItemIndex:=0;
    ListBox1Click(Sender);
    Label4.Caption:='Number of placements = ' + IntToStr(k);
  end;
end;
...

 

3.8. Program code of the interface part of the module Unit1.pas

For the purpose of verification, the following is a listing of the interface part (section interface) with the full text of the class TForm1.

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Grids, StdCtrls;

const
  MaxN = 20; // maximum number of queens and board size

type
  TArray = array [0..MaxN] of integer;

  TForm1 = class(TForm)
    Label1: TLabel;
    Edit1: TEdit;
    Button1: TButton;
    Label2: TLabel;
    ListBox1: TListBox;
    Label3: TLabel;
    StringGrid1: TStringGrid;
    Label4: TLabel;
    procedure FormActivate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure ListBox1Click(Sender: TObject);
  private
    { Private declarations }
    N:integer; // number of queens, board size
  public
    { Public declarations }
    function IsStrike(x1, y1, x2, y2:integer):boolean;
    function Strike(M:TArray; p:integer):boolean;

    // processing TStringGrid
    procedure InitStringGrid(N:integer);
    procedure ShowStringGrid(s:string; N:integer);

    // add string to ListBox1
    procedure AddToListBox(M:TArray; N:integer);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

// Implementation of procedures and functions
// ...

end.

 

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 :).

Delphi. Placement of 8 Queens. Program result

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