N-Queens results on Casio calculators

[Hlib]

The name N-Queens of the thread hints at a more general approach to the task: 5 ... 8, 9 ... N queens on 5×5 ... 8×8, 9×9 ... N×N boards with the definition of all positions in each variant:

Code:


10->R
0->Ticks% : Ticks%->U
`#CBINT
R->Dim A : R->Dim B
Wait 0 : MatBase(1)
Norm 2 : ClrText
"_"+ToStr(R)+"-queens"
"_"+ToStr(R)+"×"+ToStr(R)+"_board"
"P=" : "S=" : "t="
0->P : 0->S : 0->X
Lbl 0 : X<>R⇒Goto 5
Mat A->Mat B
Isz P : Goto 4
Lbl 5 : Isz X : R->A[X]
Lbl 1 : Isz S : X->Y
Lbl 2 : Dsz Y
A[X]-A[Y]->T⇒Goto 3
Y=0⇒Goto 0 : Goto 4
Lbl 3 : (X-Y)≠Abs T⇒Goto 2
Lbl 4 : Dsz A[X] : Goto 1
Dsz X : Goto 4
Locate 3,3,ToStr(P)+"_positions"
Locate 3,4,ToStr(S)+"_steps"
`#CBDBL
Ticks%->V : (V-U)/2^15->U
10^(3-Int log U)->V
Int (UV)/V->U
Locate 3,5,ToStr(U)+"_sec"
"END"

//ticks=1/128_sec, ticks%=1/32768_sec.

For N=10 (10->R), the calculator gives the result:
_10-gueens
_10×10 board
P=724_positions
S=348150_steps
t=177.1_sec
// Mat B=[[1,3,6,8,10,5,9,2,4,7]] is the last position 724.
For other N the calculation time t(N) for GII-2 (CBASIC) can be estimated approximately:
t(15)~10 +/- 1_days, t(20)~150 +/- 15_years.
Just for comparison, on modern laptop PC:
t(15)~10_minutes, t(20)~40_days.

If we need to have a record of all the positions in each variant, then the program code should be slightly changed (after Lbl 0):

Code:


10->R
0->Ticks% : Ticks%->U
`#CBINT
R->Dim A.B : R->Dim B.B
Wait 0 : MatBase(1)
Norm 2 : ClrText
"_"+ToStr(R)+"-queens"
"_"+ToStr(R)+"×"+ToStr(R)+"_board"
"P=" : "S=" : "t="
0->P : 0->S : 0->X
Lbl 0 : X<>R⇒Goto 5
If P
  Then Augment(Mat B, Mat A)->Mat B
    Else Mat A->Mat B
IfEnd
Isz P : Goto 4
Lbl 5 : Isz X : R->A[X]
Lbl 1 : Isz S : X->Y
Lbl 2 : Dsz Y
A[X]-A[Y]->T⇒Goto 3
Y=0⇒Goto 0 : Goto 4
Lbl 3 : (X-Y)≠Abs T⇒Goto 2
Lbl 4 : Dsz A[X] : Goto 1
Dsz X : Goto 4
Locate 3,3,ToStr(P)+"_positions"
Locate 3,4,ToStr(S)+"_steps"
`#CBDBL
Ticks%->V : (V-U)/2^15->U
10^(3-Int log U)->V
Int (UV)/V->U
Locate 3,5,ToStr(U)+"_sec"
"END"

//In this code R->Dim Mat A.B defines binary-type matrix to save RAM.

Example for N=11, GII-2(CBASIC):
P=2680_positions
S=1806706_steps
t=2741_sec
Mat B is the array of all positions.
This is the limit for CASIO, as the array with the results 8_rows×2680_columns=21440_cells and more dramatically reduces performance. The option without recording all positions gives t(11)=984_sec (i.e. ×2.8 times faster).
In my opinion, the second version of the program (complete 10-queens benchmark) is very well suited for testing modern fast calculators. It checks not only the speed of calculations, but also manipulations with a large array of data.