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.

[John Keith]

(08-28-2024 08:19 PM)Hlib Wrote:  ...
Just for comparison, on modern laptop PC:
t(15)~10_minutes, t(20)~40_days.

...

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.

As you have shown, this simple algorithm is impractical for n queens where n is greater than 12 or 14. Modern algorithms such as simulated annealing and its variants, or Knuth's Algorithm X, can find solutions for n in the thousands very quickly. See many references on Wikipedia. I would suggest that one of the modern algorithms might be more suited to testing modern calculators because they do more than just moving stuff around in memory.

[toml_12953]

(08-29-2024 12:18 PM)John Keith Wrote:  As you have shown, this simple algorithm is impractical for n queens where n is greater than 12 or 14. Modern algorithms such as simulated annealing and its variants, or Knuth's Algorithm X, can find solutions for n in the thousands very quickly. See many references on Wikipedia. I would suggest that one of the modern algorithms might be more suited to testing modern calculators because they do more than just moving stuff around in memory.

That's fine as long as you don't compare the times measured using the new algorithms with those measured with the old when comparing hardware. If you just want to compare the old algorithm with the new, then that's a valid comparison.