Programming the Queens (Linked-In) puzzle.
download Queens program
download Queens Delphi project

Look here for a description of the Queens puzzle helper.

This article describes the Queens Delphi-7 programming project.

Operation

There are two modes of operation: NEW and PLAY.
The NEW mode allows selection of the puzzle size and painting of the regions.
The PLAY mode enables placing an "X" in cells that cannot hold a queen and the placing of queens.
Warnings, hints and autoX may be selected.
AutoX means that in case of a new queen all connected cells are set to "X".
A warning occurs when more than one queen occupies a column, row or region
or when columns, rows and regions have no open cell left, so cannot hold a queen.

The project has 3 units:
    1. unit1: control, events handling, painting
    2. game_unit: warnings, hints, game specific procedures
    3. io_unit: save and open procedures

Drawing

Drawing of the game is done on bitmap map.
This bitmap is made visible by copying it's contents to paintbox1 on form1.

Setting the size of a game: 
procedure ResizeGame(newGS : byte); //newGS is the new game size.
A cell counts 48*48 pixels. A n*n game has a width (and height) of n*48 + 1 pixels.



Cell data is stored in a one-dimensional array Game[ ]. 
type TCellstatus = (clClosed,clOpen,clQueen);
     TCell = record
              status   : Tcellstatus;
              region   : byte;
              colorNr  : byte;
              Gcol     : byte;
              Grow     : byte;
              Qlev     : byte;  //# queens closing cell
              Hint     : byte; //0: nono; 1:X; 2:Queen
......       end;
var game  : array[1..144] of TCell;//maximum is 12*12 puzzle
    gamesize : byte = 8;
    gamesize2 : byte = 64;//gamesize*gamesize
Cells are counted 1...gamesize*gamesize: left to right, top to bottom.

Around paintbox1 edges are paint on the form1 canvas. 
procedure paintedges(ct : Tcontrol; w : byte; col : longword);
//line around control, penwidth w
var i : byte;
    par : TComponent;
    x1,y1,x2,y2 : word;
begin
 par := ct.getParentcomponent;
 with Tcustomform(par) do with canvas do
  begin
   x1 := ct.left-w;
   y1 := ct.top-w;
   x2 := ct.left+ct.width+w-1;
   y2 := ct.top+ct.height+w-1;
   pen.width := 1;
   pen.color := col;
   for i:= 0 to w-1 do
    begin
     moveto(x1+i,y1+i);
     lineto(x1+i,y2-i);
     lineto(x2-i,y2-i);
     lineto(x2-i,y1+i);
     lineto(x1+i,y1+i);
    end;
  end;
end;
Provide rectangle of a cell: 
function Cell2Rect(nr : byte) : Trect;
//nr : game cell nr
var x,y : word;
begin
 dec(nr);
 x := (nr mod gamesize)*48;
 y := (nr div gamesize)*48;
 result.Left := x + 1;
 result.Right := x + 47;
 result.Top := y + 1;
 result.Bottom := y + 47;
end;
Copy complete map or single cell to paintbox1: 
procedure map2box;
begin
 form1.gamebox.Canvas.Draw(0,0,map);
end; 
......
procedure Cell2Box(n : byte);//copy cell n to paintbox1
var r : Trect;
begin
 r :=Cell2Rect(n);
 form1.gamebox.Canvas.CopyRect(r,map.Canvas,r);
end;
Regions are painted by
    - selection of a color by mouseclick on the color box
    - Move mouse over game paintbox while holding down the left-mousebutton.
Notice the variables region and colorNr.
The choice is of 15 colors in any sequence. (colorNrs 1..15).
For hint generation this is very inconvenient so, these color numbers are converted to
region numbers counting sequentially 1..gamesize.
This is done when switching from NEW to PLAY mode.

function MakeRegions : Ttestresult;
Does the job. Testresult may indicate unassigned cells or the number of regions
being unequal to the gamesize.

Extra lines are painted between cells of different color.
This is done by: 
procedure paintfences;

Data structures

type TCellstatus = (clClosed,clOpen,clQueen);//closed is X or Q
     TCell = record
              status   : Tcellstatus;
              region   : byte;
              colorNr  : byte;//index into colorbox
              Gcol     : byte;//column of cell
              Grow     : byte;//row of cell
              Qlev     : byte;  //# queens closing the cell
              Hint     : byte; //0: none; 1:X; 2:Queen
             end;
ColorNr is the index of the color in the colorbox.
Procedure EnterPlayMode calls function makeRegions : Ttestresult;
Tests for unassigned cells and also the number of regions being equal to the number of columns.

Gcol,Grow are the column and row numbers of teh cell (1..gamesize).
Qlev counts 1,2,... .
When AutoX is selected, placing a queen automatically places "X" s in cells of the same
column, row or region.
For these automaticalle closed cells Qlev is increased.
A cell may only be modified if Qlev=0. So all queens closing the cell have to be removed.

Calculate column and row from cell number: 
procedure cell2CR(var C,R : byte; n : byte); //calc column (C), row (R) from cell (n)
begin
 C := ((n-1) mod gamesize) + 1;
 R := ((n-1) div gamesize) + 1;
end;

Testresult

type  TTestresult = record
                    Scode : byte;  //summary
                    Ecode : byte;  //error code
                    n1,n2 : byte;  //cells
                   end;
Scode values:
    0 : OK
    1 : unassigned cells (no region)
    2 : region count unequal to gamesize

Connected cells

Cells that are in the same column, row, region or cells that touch diagonally are called "connected". 
function connected(a,b : byte) : boolean;                   
var c1,c2,r1,r2 : byte;
begin
 result := false;
 if a=b then exit;
//
 c1 := (a-1) mod gamesize;//Gcol,Grow used in later versions
 r1 := (a-1) div gamesize;
 c2 := (b-1) mod gamesize;
 r2 := (b-1) div gamesize;
 result := (game[a].region = game[b].region) or
           (c1 = c2) or  (r1 = r2) or
           ((abs(r1-r2) = 1) and (abs(c1-c2) = 1));
end;
Provides "true" if cells a,b are connected.

Strategy

Function TestGame : Ttestresult does the job.
Note : testresult values differ from previous values.
Scode:
    bit 0: game OK
    bit 1: game is full
    bit 2: all queens placed
Ecode
    1 : column n1 is closed
    2 : row n1 is closed
    3 : region n1 is closed
    5 : multiple queens in column n1
    6 : multiple queens in row n1
    7 : multiple queens in region n1
    8 : touching queens in cells n1, n2
In case of a warning, procedure procWarnings builds text from above error codes.

Queens is a logical puzzle.
The following rules apply:
    1. Cells that connect to a queen cannot hold a queen.
    2. If a column (or row) lies inside a region then all cells of the region outside the column(row) cannot hold a queen.
    3. If a region lies within a column(row) then all cells of the column(row) outside the region cannot hold a queen.
    4. Queens cannot be placed such that they close another column, row or region.
    5. If n regions are positioned inside n colums(or rows) then any cell of other regions in these columns(rows) cannot hold a queen.
Situations 4,5 may be hard to recognize.

Some examples:
yellow column within regionyellow,purple regions within columnyellow and red regions in columns 3,4

In the left image, "X" 's could be placed as well considering that
the red, grey, blue and green regions occupy the 4 columns 2,3,4,5.

X: queen would close regiononly place for queen
"X": queen would close region

Warnings

Active in PLAY mode. Checks game after move for:
    multiple queen in column, row or region
    full columns, rows or cells (no space to place queen).
Function TestGame : TTestresult;// does the job.
This function also tests for solutions. See TTestresult codes before.

Hints

Hint search start by a clikck on the hint (lamp) button.
procGametest is called and if no errors are detected procHints is called.
The hint procedures put their results in variable hintresult: 
type THintResult = record
                    test   : byte;  //hint number
                    nr     : byte;  //cell
                    column : byte;
                    row    : byte;
                    region : byte;
                    crg    : word;  //column,row,region bit vector
                   end;
There are 2 kind of hints: hintX idicates cell(s) that cannot hold a queen ("X").
HintQ: cell that must hold a queen.

procHints calls:
    procHint1: checks for open cells in columns, rows or regions that hold a queen.
      calls functions testColumn, testRow,testRegion which return data in format TCRGstate
      which is a SET of TCellstatus.
    procHint2: test for closed ("X") cells diagonal to a queen.
    procHint31, procHint32, procHint33: test cell for queen closing a column (31), row (32) or region (33)
      these procedures call functions checkColumnConnection(Xcolumn,cell)
      checkRowConnection(Xrow,cell) and checkRegionConnection(Xregion,cell)
      which return true if the cell connects to all cells in the column, row or region.
    procHint51, procHint52 : checks for n columns (51) or rows (52) holding n regions.
ProcHint51,procHint52 could be combined in future releases.
Thise is the more complicated part of the hints.

Let's have a closer view at procedure procHint51. 
variable fullmask : word;
has bits 1..n set for gamesize n. 
 
var regioncolumns : array[1..gamesize] of word;
bit c set in regioncolumns[r] means that region r has a cell positioned in column c.
Then k (2...gamesize-1) columns are selected by procedure combinations.
Look here for a description of the combinations generator.
A next (inner) loop selects k regions.
Selected columns and regions are bitwise coded (bit set if present).
Using predefined regionColumns and the selected combination, variable selRegions is made.
SelRegions has bit c set if the selected regions have an open cell in column c.
So, if selColumns = selRegions then in other regions of cells within the selected columns
and "X" may be placed.
This is done by procedure Xscan(selColumns,fullMask,XRegMask xor fullMask)
selcolumns: bit set if column selected.
fullmask: select all rows (in case of column testing)
Xregmask: bit set if region selected.
XregMask xor fullmask: alle regions that were not selected.

Xscan tests all cells and if criteria are satisfied, Hmarkcell(cell,1) is called to place an "X" in the cell.
note: 1: place X; 2: place queen.

I/O, save and open games

Queen files do not have an extention.
Instead, the file name is prefixed by Q_ .
I/O is done by blockread and blockwrite procedures.
Before saving a game, cell data is entered in 
var buffer : array[0..147] of longword;
    bix : byte;
bix is the wordcount in the buffer.
  I/O format   (longwords)

  0    ---- ---e ---- ---e ---- ---u ---- ---Q
  1    --version ---- size ---- ---s ---- ---n
  2    ---- Qlev ----color ---region ---status      cell 1
  3    .......................................
  ....                                              cell n*n
       ---f ---f ---0 ---0 ---0 ---0 ---0 ---0      end of data
function loadbuffer fills the buffer with game data,
function UnpackBuffer supplies the data of the opened game.
Here follows the saveGame function: 
function saveGame : byte;
var fname,fdir : string;
    f : file;
    xf : integer;
begin
 result := 2;
 clearbuffer;
 loadbuffer;
 with form1.savedialog1 do
  if execute then
   begin
    result := 1;
    fname := ExtractFileName(filename);
    fdir := ExtractFileDir(filename);
    if pos('Q_',fname) <> 1 then insert('Q_',fname,1);
    filename := fdir + '\'+ fname;
{$I+}
    try
     assignfile(f,filename);
     rewrite(f,4);           //4: record size
     blockwrite(f,buffer,bix,xf);
     result := 0;
    finally
     CloseFile(f);
    end;
   end;
end;
This concludes the Queens Delphi project description.