Queens

# 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

 01  LBL "2DNQ"  02  RCL 00  03  STO M  04  6  05  MOD  06  X=0?  07  GTO 02  08  3  09  -  10  X=0?  11  GTO 04  12  ABS  13  1  14  X=Y?  15  GTO 06  16  LBL 01  17  RCL M  18  ST+ X  19  RCL 00  20  MOD  21  1  22  +  23  STO IND M  24  DSE M  25  GTO 01  26  GTO 08  27  LBL 02  28  2 29  ST/ M  30  LBL 03  31  RCL 00  32  2  33  /  34  RCL M  35  ST+ Y  36  ST+ X  37  STO IND M  38  DSE X  39  STO IND Y  40  DSE M  41  GTO 03  42  GTO 08  43  LBL 04  44  RCL 00  45  1  46  STO 01  47  -  48  2  49  /  50  STO M  51  LBL 05  52  SIGN  53  RCL M  54  ST+ Y  55  RCL 00  56  1 57  +  58  2  59  /  60  ST+ Y  61  RCL M  62  ST+ X  63  +  64  STO N  65  RCL 00  66  DSE X  67  MOD  68  X=0?  69  X<> L  70  1  71  +  72  STO IND Y  73  CLX  74  X<> N  75  3  76  -  77  RCL 00  78  DSE X  79  MOD  80  X=0?  81  X<> L  82  1  83  +  84  STO IND Z 85  DSE M  86  GTO 05  87  GTO 08  88  LBL 06  89  2  90  ST/ M  91  LBL 07  92  RCL M  93  RCL 00  94  2  95  /  96  ST+ Y  97  LASTX  98  -  99  RCL M 100  ST+ X 101  + 102  STO Z 103  RCL 00 104  MOD 105  X=0? 106  X<> L 107  STO IND M 108  R^ 109  3 110  + 111  RCL 00 112  MOD 113  X=0? 114  X<> L 115  STO IND Z 116  DSE M 117  GTO 07 118  LBL 08 119  9 120  RCL 00 121  X>Y? 122  GTO 10 123   E3 124  / 125  ISG X 126  0 127  LBL 09 128  10 129  * 130  RCL IND Y 131  + 132  ISG Y 133  GTO 09 134  LBL 10 135  RCL 00 136   E3 137  / 138  ISG X 139  END

( 208 bytes / SIZE N+1 )

 STACK INPUTS OUTPUTS Y / Solution X / 1.nnn

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:

 Q Q Q Q Q Q Q Q

-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: /

 01  LBL "QUEEN"  02  " N=?"  03  PROMPT  04  STO 00  05   E3  06  /  07  ISG X  08  LBL 09  09  FIX 0  10  CF 29  11  " Q"  12  ARCL X  13  FIX 04  14  SF 29  15  >"=?"  16  PROMPT  17  FC?C 22  18  GTO 00  19  STO IND Y 20  X<>Y  21  ISG X  22  GTO 09  23  LBL 00  24  CLRGX  25  INT  26  STO M  27  LBL 01  28  CLX  29  SIGN  30  STO IND M     31  LBL 02  32  RCL M  33  X<>Y  34  -  35  STO N  36  LBL 03  37  RCL IND M  38  RCL IND N 39  X=Y?  40  GTO 04  41  -  42  ABS  43  RCL M  44  RCL N  45  -  46  X=Y?  47  GTO 04  48  DSE N  49  GTO 03            50  RCL M  51  RCL 00  52  X=Y?  53  GTO 05  54  SIGN  55  +  56  STO M  57  GTO 01 58  LBL 04  59  RCL IND M  60  RCL 00  61  X=Y?  62  GTO 00  63  SIGN  64  ST+ IND M  65  GTO 02  66  LBL 00  67  CLX  68  STO IND M     69  SIGN  70  ST- M  71  RCL M  72  X#0?  73  GTO 04  74  " NO SOL"  75  TONE 9  76  PROMPT 77  LBL 05  78  RCL 00  79   E3  80  /  81  ISG X  82  0  83  LBL 06  84  10  85  *  86  RCL IND Y     87  +  88  ISG Y  89  GTO 06  90  X<>Y  91  RCL 00  92  -  93  CLA  94  BEEP  95  END

( 165 bytes / SIZE nnn+1 )

 STACK INPUTS PROMPTs OUTPUTS Y / / Solution X / .................. 1.nnn

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:

 Q Q Q Q Q Q Q Q

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:

 Q Q Q Q Q Q Q Q Q Q Q

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: /

 01  LBL "QUEEN2"  02  " N=?"  03  PROMPT  04  STO 00  05   E3  06  /  07  ISG X  08  LBL 09  09  FIX 0  10  CF 29  11  " Q"  12  ARCL X  13  FIX 04  14  SF 29  15  >"=?"  16  PROMPT  17  STO IND Y        18  X<>Y  19  ISG X  20  GTO 09  21  1  22  +  23  " RAND?"  24  PROMPT  25  STO IND Y  26  LBL 10  27  CLA  28  RCL 00  29   E3  30  / 31  2  32  +  33  STO N  34  1.001  35  -  36  STO M  37  LBL 01  38  RCL IND M  39  RCL IND N        40  -  41  ABS  42  RCL M  43  INT  44  RCL N  45  INT  46  -  47  ABS  48  X=Y?  49  ISG O  50  CLX  51  ISG N  52  GTO 01  53  RCL N  54  FRC  55  RCL M  56  INT  57  2  58  +  59  +  60  STO N 61  ISG M  62  GTO 01  63  RCL 00  64  1  65  +  66  RCL O  67  STO IND Y        68  VIEW X  69  LBL 02  70  RCL 00  71  2  72  +  73  RCL IND X  74  R-D  75  FRC  76  STO IND Y  77  RCL 00  78  *  79  INT  80  STO M  81  ENTER  82  LBL 03  83  CLX  84  RCL IND Z  85  R-D  86  FRC  87  STO IND Z  88  RCL 00  89  *  90  INT 91  X=Y?  92  GTO 03  93  1  94  ST+ M  95  +  96  STO N  97  CLX  98  XEQ 14  99  RCL N 100  X<> M 101  STO N 102  X<>Y 103  XEQ 14 104  RCL IND M 105  X<> IND N 106  STO IND M      107  X<>Y 108  CHS 109  XEQ 14 110  RCL N 111  X<> M 112  STO N 113  X<>Y 114  XEQ 14 115  X<=0? 116  GTO 00 117  RCL IND M 118  X<> IND N 119  STO IND M 120  RCL 00 121  1 122  + 123  RCL IND X 124  VIEW X 125  GTO 02 126  LBL 00 127  RCL 00 128  1 129  + 130  X<>Y 131  RCL IND Y 132  + 133  STO IND Y      134  VIEW X 135  X=0? 136  GTO 12 137  GTO 02 138  LBL 14 139  RCL 00 140  STO O 141  X<>Y 142  LBL 11 143  RCL M 144  RCL O 145  X=Y? 146  GTO 11 147  - 148  ABS 149  RCL IND M 150  RCL IND O 151  - 152  ABS 153  X=Y? 154  ISG Z 155  LBL 11 156  X<> Z 157  DSE O 158  GTO 11 159  RTN 160  LBL 12 161  RCL 00 162   E3 163  / 164  ISG X 165  0 166  LBL 13 167  10 168  * 169  RCL IND Y      170  + 171  ISG Y 172  GTO 13 173  X<>Y 174  RCL 00 175  - 176  CLD 177  CLA 178  BEEP 179  END

( 291 bytes / SIZE nnn+2 )

 STACK INPUTS PROMPTs OUTPUTS Y / / Solution X / .................. 1.nnn

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:

 Q Q Q Q Q Q Q Q

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

ai,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 = a1,1  .....................  Rn^2 = an,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: /

 01  LBL "3DN2Q"  02  RCL 00            03  X^2  04  LBL 11  05  ENTER  06  DSE X  07  INT 08  STO Z  09  RCL 00            10  ST/ T  11  MOD  12  1  13  +  14  3 15  *  16  R^  17  INT                 18  1  19  +  20  5  21  * 22  +  23  RCL 00            24  MOD  25  X=0?  26  X<> L  27  FC? 00  28  STO IND Y 29  FS? 01  30  VIEW X  31  X<>Y  32  DSE X  33  GTO 11           34  END

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

 STACK INPUT OUTPUT X / 0

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 = a1,1  .....................   •  Rn^2 = an,n

Flags: /
Subroutines: /

 01  LBL "3DN2Q?"  02  CLA  03  RCL 00             04  DSE X  05  STO M  06  LBL 01  07  RCL 00  08  STO N  09  LBL 02  10  RCL 00  11  RCL M  12  -  13  STO O  14  LBL 03  15  RCL N  16  RCL 00  17  ST* Y  18  -  19  STO Y  20  RCL M  21  ST+ Z  22  +  23  RCL O  24  +  25  RCL IND Y  26  RCL IND Y  27  - 28  X=0?  29  ISG P  30  ""  31  ABS  32  RCL O  33  X=Y?  34  ISG P  35  CLX  36  DSE O  37  GTO 03  38  DSE N  39  GTO 02  40  DSE M  41  GTO 01  42  RCL 00             43  STO M  44  LBL 04  45  RCL 00  46  DSE X  47  STO N  48  LBL 05  49  RCL 00  50  RCL N  51  -  52  STO O  53  LBL 06  54  RCL N 55  RCL O  56  +  57  RCL 00  58  ST* Y  59  -  60  RCL N  61  RCL 00             62  ST* Y  63  -  64  RCL M  65  ST+ Z  66  +  67  RCL IND Y  68  RCL IND Y  69  -  70  X=0?  71  ISG P  72  ""  73  ABS  74  RCL O  75  X=Y?  76  ISG P  77  CLX  78  DSE O  79  GTO 06  80  DSE N  81  GTO 05 82  DSE M  83  GTO 04  84  RCL 00             85  DSE X  86  STO M  87  LBL 07  88  RCL 00  89  DSE X  90  STO N  91  LBL 08  92  RCL 00  93  RCL M  94  -  95  RCL 00  96  RCL N  97  -  98  X>Y?  99  X<>Y 100  STO O 101  LBL 09 102  RCL N 103  RCL 00 104  ST* Y 105  - 106  RCL N 107  RCL O 108  + 109  RCL 00 110  ST* Y 111  - 112  RCL M 113  ST+ Z 114  + 115  RCL O 116  + 117  RCL IND Y 118  RCL IND Y 119  - 120  X=0? 121  ISG P 122  "" 123  ABS 124  RCL O 125  X=Y? 126  ISG P 127  CLX 128  DSE O 129  GTO 09 130  DSE N 131  GTO 08 132  DSE M 133  GTO 07 134  RCL 00           135  STO M 136  LBL 10 137  RCL 00 138  DSE X 139  STO N 140  LBL 11 141  RCL M 142  DSE X 143  RCL 00 144  RCL N 145  - 146  X>Y? 147  X<>Y 148  STO O 149  LBL 12 150  RCL N 151  RCL O 152  + 153  RCL 00           154  ST* Y 155  - 156  RCL O 157  - 158  RCL N 159  RCL 00 160  ST* Y 161  - 162  RCL M 163  ST+ Z 164  + 165  RCL IND Y 166  RCL IND Y 167  - 168  X=0? 169  ISG P 170  "" 171  ABS 172  RCL O 173  X=Y? 174  ISG P 175  CLX 176  DSE O 177  GTO 12 178  DSE N 179  GTO 11 180  SIGN 181  ST- M 182  RCL M 183  X>Y? 184  GTO 10           185  RCL P 186  CLA 187  END

( 297 bytes / SIZE 1+N^2 )

 STACK INPUT OUTPUT X / k

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