The N-Queens Problem for the HP-41

Overview
 

 1°)  One Solution
 2°)  Backtracking
 3°)  A Random Method
 4°)  3D N^2-Queens Problem

    a)  One Solution
    b)  A Test
 

-The programs listed in §1 to §3 try to place n queens on an nxn chessboard so that no queen attacks another
-For a classical chessboard, n = 8

-There is no solution if n = 2 or n = 3
-If n = 1 , the solution is obvious and we assume n > 3 in the following routines.

-In paragraph 4, we deal with cubic NxNxN chessboards to place N^2 queens so that no queen attacks another
 

1°)  One Solution
 

 "2DNQ" gives one solution to this puzzle
 It uses the method of Fresnel given in reference [1]
 The formulae depend on  N mod 6
 

-The position of a queen in column k ( in register Rkk ) is given by its row
-For example, if R02 = 7 , there is a queen in column 2 , row 7
 ( you can of course use a different convention like row 2 , column 7 if you prefer... )
 
 

Data Registers:           •  R00 = n > 3                         ( Register R00 is to be initialized before executing "2DNQ" )

                                          R01 = Q1  .....................  Rnn = QN

Flags: /
Subroutines: /

-Lines 15 and 26 are three-byte GTO's
 
 

 
            ( 208 bytes / SIZE N+1 )
 
 

  Where Solution is an n-digit number  if  n  <  10  ( meaningless otherwise )

Examples:

   N = 4  XEQ "2DNQ"  >>>>   1.004   X<>Y   2413

-Likewise,

   N = 5  ->  35241
   N = 6  ->  246135
   N = 7  ->  3572461
   N = 8  ->  46827135
   N = 9  ->  157938246

-With N = 8 , the solution means:
 
 

 
-I f N > 9 , Y-output is meaningless but you find the place of the queens in registers R01 thru Rnn
 

2°)  Backtracking
 

-Here you place - at least - one queen on the 1st column, and your HP-41 will give you 1 solution to the problem.

-The position of a queen in column k ( in register Rkk ) is given by its row
-For example, if R02 = 7 , there is a queen in column 2 , row 7
 ( you can of course use a different convention like row 2 , column 7 if you prefer... )
 

Data Registers:     R00 = n > 3

                                R01 = Q1  R02 = Q2  ....................  Rnn = Qn
Flags: /
Subroutines: /
 
 
 
 
 

 
    ( 165 bytes / SIZE nnn+1 )
 
 

    Where  Solution is an n-digit number  if  n  <  10  ( meaningless otherwise )

Example1:    With  n = 8 , place a 1st queen in column 1 , row 4
 

  XEQ "QUEEN"   >>>>    N =?

             8                R/S      Q1=?
             4                R/S      Q2=?                              Press R/S without any digit entry when you have placed all the queens you want

                               R/S      >>>>   1.008                               ---Execution time = 3mn00s---
                                          X<>Y   41582736

-Thus, the HP41 has found the solution below:
 
 

 
Example2:    With  n = 11 , place a 1st queen in column 1 , row 4  and a 2nd queen in column 2 , raw 11
 

  XEQ "QUEEN"   >>>>     N =?
            11                R/S      Q1=?

             4                 R/S      Q2=?
            11                R/S      Q3=?                             Press R/S without any digit entry when you have placed all the queens you want

                               R/S      >>>>   1.011                               ---Execution time = 10mn42s---
 

  Y-output is meaningless if n > 9  but you find in R01 thru R11:

   4   11  1   3   9   6   8   10   2   7   5    which gives the following solution:
 
 

 
Warning:

-The HP-41 does not check that the queens you place in the first columns do not attack each other
-In this case, the solution may be wrong !

-Execution time becomes prohibitive for large n-values.
 

3°)  A Random Method
 

-In this variant, you store a permutation of  { 1 , 2 , ........ , n }  into R01  R02  ..................  Rnn
-Then, "QUEEN2" randomly swaps 2 queens until the puzzle is solved

-The HP-41 displays the number of pairs of queens which attack each other
-When "0" is displayed, we have a solution ! ( "1" or "2" may be displayed many times before "0" )
 

Data Registers:     R00 = n > 3

                                R01 = Q1  R02 = Q2  ....................  Rnn = Qn         Rn+1: temp   Rn+2 = random numbers
Flags: /
Subroutines: /
 
 
 

 
     ( 291 bytes / SIZE nnn+2 )
 
 

    Where  Solution is an n-digit number  if  n  <  10  ( meaningless otherwise )

Example:   On a classical 8x8 chessboard

   XEQ "QUEEN2"   >>>     N=?
              8                 R/S      Q1=?           If you start with 8 queens on the diagonal

              1                 R/S      Q2=?
              2                 R/S      Q3=?
              3                 R/S      Q4=?
              4                 R/S      Q5=?
              5                 R/S      Q6=?
              6                 R/S      Q7=?
              7                 R/S      Q8=?
              8                 R/S      RAND?        And if you choose 1 as random seed

              1                 R/S      >>>>>          HP-41 displays 28  16  11  9  7  5  ..................  1  1  1 ............  0

                       and eventually                     1.008                             ---Execution time = 8mn---
                               X<>Y                        58417263

So, a solution has been found:
 
 

 
Notes:

-Use a good emulator in turbo mode !
-With n = 25 , if you start with R01 = 1  R02 = 2 ................... R25 = 25  and random seed = 1, you'll find in R01 thru R25

  14  7  18  6  24  22  15  4  21  10  12  2  5  25  19  11  23  1  17  13  3  9  20  8  16     ( in 52 seconds with V41 turbo )
 

4°)  3D N^2-Queens Problem
 

     a)  One Solution
 

-Here the levels of the queens are stored from R01 thru Rn^2  ( if Flag F00 is clear )
-The 1st column is stored in R01 to Rnn,
  the 2nd column in Rn+1 to R2n,
  ..............
  the n-th column in Rn^2-n+1 to Rn^2   ( replace "column" by "row" if you prefer )

-The formula - also given in reference 1 - assumes that gcd( n, 210 ) = 1

   a_i,j = 3 i + 5 j  mod n

-So, n = 11 is the smallest interesting case.
 

Data Registers:           •  R00 = n  such that  gcd( n , 210 ) = 1         ( Register R00 is to be initialized before executing "3DN2Q" )

                                          R01 = a_1,1  .....................  Rn^2 = a_n,n    if  CF 00

Flags:   F00-F01              CF 00 ->  The positions of the queens are stored into R01 .....
                                          SF 00  ->  R01.... are not used

                                          CF 01  -> The positions of the queens are not displayed
                                          SF 01  -> The positions of the queens are displayed
Subroutines: /
 
 

 
    ( 54 bytes / SIZE 001 or 1+N^2 )
 
 

 
Example:    With  n = 13

    CF 00
    13  STO 00  XEQ "3DN2Q"  >>>>   0   and we find in registers R01 to R169
 

   8   13   5   10   2    7   12   4    9    1    6   11   3
  11   3    8   13   5   10   2    7   12   4    9    1    6
   1    6   11   3    8   13   5   10   2    7   12   4    9
   4    9    1    6   11   3    8   13   5   10   2    7   12
   7   12   4    9    1    6   11   3    8   13   5   10   2
  10   2    7   12   4    9    1    6   11   3    8   13   5
  13   5   10   2    7   12   4    9    1    6   11   3    8
   3    8   13   5   10   2    7   12   4    9    1    6   11
   6   11   3    8   13   5   10   2    7   12   4    9    1
   9    1    6   11   3    8   13   5   10   2    7   12   4
  12   4    9    1    6   11   3    8   13   5   10   2    7
   2    7   12   4    9    1    6   11   3    8   13   5   10
   5   10   2    7   12   4    9    1    6   11   3    8   13
 

Note:

-If SF 00 & SF 01, these numbers are successively displayed ( from the last to the first ) without using registers R01 ................
-"Preferable" for large n-values, especially if n > 17...
 

     b)  A Test
 

-This program simply checks that you've found a solution - or not.

-Store the levels of the n^2 queens into R01 to Rn^2
-Store n into R00 and XEQ "3DN2Q?"

  If HP41 returns 0 you had found a solution to the puzzle
  Otherwise, at least 2 queens attack each other
 

Data Registers:           •  R00 = n > 1                       ( Registers R00 thru Rn^2 are to be initialized before executing "3DN2Q?" )

                                      •  R01 = a_1,1  .....................   •  Rn^2 = a_n,n

Flags: /
Subroutines: /
 
 
 

 
     ( 297 bytes / SIZE 1+N^2 )
 
 

  Where k = 0 iff we have a solution.

Example:

  CF 00  11  STO 00   XEQ "3DN2Q"  ( paragraph 4-a) )

  Then  XEQ "3DN2Q?"   >>>>   0                                               ---Execution time = 23m10s---

-So, it confirms that we have a solution to the 3D N2-Queens puzzle.

Notes:

 k is the number of pairs of queens which attack each other.
 In fact, if there are - for example - 3 queens in the same row   Q1   Q2      Q3
 this routine will return 3   { Q1  Q2 }  { Q2  Q3 }  and  { Q1  Q3 }
 
 

Reference:

[1]  Jordan Bell, Brett Stevens - "A survey of known results and research areas for n-queens" - ELSEVIER