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.

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

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

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 = a_1,1 ..................... • Rn^2 = a_n,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

hp41programs

The N-Queens Problem for the HP-41