N-Queens results on Casio calculators
|
08-28-2024, 08:19 PM
(This post was last modified: 08-30-2024 06:00 PM by Hlib.)
Post: #21
|
|||
|
|||
RE: N-Queens results on Casio calculators
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:
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:
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. |
|||
08-29-2024, 12:18 PM
Post: #22
|
|||
|
|||
RE: N-Queens results on Casio calculators
(08-28-2024 08:19 PM)Hlib 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. |
|||
08-31-2024, 02:40 AM
Post: #23
|
|||
|
|||
RE: N-Queens results on Casio calculators
(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. Tom L Cui bono? |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)