DIR Return Create A Forum - Home
---------------------------------------------------------
knight tours
HTML https://knighttours.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: 8x8 knight's tours
*****************************************************
#Post#: 25--------------------------------------------------
SSD with all closed 8x8 knight's tours
By: gsgs Date: September 20, 2023, 12:31 pm
---------------------------------------------------------
I resumed my knight's tour creation project ...
if all goes well, on 10 threads, I'll have by 2023-10-05
a 4TB SSD with all 1692674826245 closed 8x8 knight's tours ;
in 41790 files compressed to 3.3 TB with 7zip.
Decompressed it will be 33 bytes per tour,
one byte for 2 directions from {0,1,2,3,4,5,6,7}.
All the 41790 files can then be decompressed into ramdrive
- one after the other - and are checked and filtered
for some property in a few hours in parallel.
It would be 3.5 times faster to create the tours with
Chalaturnyk's
program, but the compression rate is lower with that ordering of
tours.
And resorting them was not so easy on 10 threads in parallel.
----------------------------------
Post your suggestions, what properties should be examined !
statistics of move-direction-counts
statistics of magic lines ( modulo 8 )
number of Posa rotations that give other closed or open tours
number of crossings
number of short cycles
----------------------------
create an ordering where almost each tour is a Posa-rotation of
the preceding tour. Then the tours can be stored with less than
one byte per tour
============edit 2023-09-25=================
I'm rethinking the whole project, since I found an even
better compression of knight's tours :
view a closed 8x8 knight's tour as a 64-subset of the 168 edges
represented by a binary vector of 168-bits=21 bytes.
Sorting these vectors and compressing them with 7zip
gives a rate about 1 byte per tour.
===edit again=== <0.5 bytes per tour when storing differences of
consecutive sorted 168-bit sets and then compressing them with
7zip -mx=7
==> <1 TB for all closed tours. Although, decompressing them
into "normal" moves may take 500 cycles per tour or 4 days on 1
core
Again a much faster and better method was found only after
the initial project was almost finished already.
I see, there are meanwhile also 2TB micro-SDs available, reading
160MB/s
2TB being the physical maximum for micro SDs, so there will be
no 4TB
==================================================
update 2023-10-06
calculations have finished as expected, but 38 of the 41790
.7z files are not recognized by 7zip.
Presumably data errors on the SSDs.
I didn't experience such things on HDs in the last 2 decades.
I'm rerunning some file-creations hoping that the other archives
which can be opened, are ok. And then I'll have to remove
symmetrical doublettes, which will take 3 days ...
-------------update 2023-10-07------------------------
after redoing the ranges with 7zip-errors , it now reports
3.066 TB in total before deleting doubles, so I expect
a final 3.004 TB or a compression rate of 1.812 bytes per tour
-------------update 2023-10-23------------------------
I think, I probably have the 41790 compressed files
with the 1658420855433=1.7e12 tours on a nvme-4TB SSD.
But I had several data errors and the correctness of
the files is not yet verified.
I have no reliable copy yet, 2 ironwolf HDs collapsed
in the process, one just had a backup , the other presumably
from permanent non-sequential access to the 41790 files.
On used some msata-SSDs in sata-adapters to create the
tours but had some unexplained data-errors too.
And hard to find frequent errors from DOS's ascii-13 in
linux-files.
So I ordered an 4TB Samsong EVO 870 SSD with old sata3
connections now,
to communicate/copy with the 4TB-nvme-SSD . Let's see ...
I still think that storing the tours as compressed
edge-168-bit-vectors gives much better compression rates :
0.7 bytes per tour, when sorted and stored as xors
of consecutive bit-vectors before compressing them with 7zip.
These vectors fit into 256-bit extended registers
and can be quickly manipulated with Intel-256-bit commands,
e.g. for counting jump-directions or crossings or Posa-rotations
but it's slower to convert them to normal vertice-based
tour-format.
The ultimative goal is handle them massively in
parallel on graphic-cards ...
#Post#: 30--------------------------------------------------
Re: SSD with all closed 8x8 knight's tours
By: gsgs Date: December 13, 2023, 3:28 am
---------------------------------------------------------
a first run confirmed the correctness of the data,
(after rerunning 2 of the 41790 ranges)
extracted the 1658420855433 closed 8x8-tours from the
41790 compressed files totalling 3.1TB.
It computed the row and column sums modulo 8
and made the statistics of linesums equal to 4 (mod 8 )
and printed the 293212167 tours which are semimagic
modulo 8, meaning, that all 8 rowsums modulo 8 are equal to 4.
This took 5 days on 8 threads or nearly 6000 CPU-cycles
per tour. For simple calculations some hundred cycles per
tour should be sufficient, so there is room for
speed-improvement.
The total statistics of rows/columns equal to 4 mod 8 is :
[code]
16838714252, 88158926161,103929326657, 68311192703,30629120855,
7014055409,1948763279,0,31700885
0,116087686713,272999397213,179566861582,80410597679,18593856103
,4996171426,0,73510953
0,
0,160945523428,211693446799,94739662128,21723530863,5962801013,0
,92493498
0, 0, 0,
69634193705,62322388067,14311301446,3911995448,0,59555175
0, 0, 0, 0,13982775616,
6436843058,1765081630,0,28116546
0, 0, 0, 0, 0,
762444958, 389440547,0, 5158351
0, 0, 0, 0, 0,
0, 61544528,0, 2530393
0, 0, 0, 0, 0,
0, 0,0, 0
0, 0, 0, 0, 0,
0, 0,0, 146366
matrix A(i,j) = number of closed 8x8 knight's tours
symmetry-classes with
i of its rows summing to 4 (mod 8)
j of its columns summing to 4 (mod 8)
the tours are rotated such that at least as many columns as rows
sum to 4 (mod 8)
146366 closed 8x8 knight's tours are "magic" modulo 8
(no matter at which square you start)
[/code]
there are 750464 closed 8x8 knight's tours where all
8 rows sum to 252 (plus their rotated,reflected,reversed ones)
There are 5022,89912,10551,91354,5243,20675,388,1940,4
tours where all 8 rows or columns sum to 252 for
1,2,3,4,5,6,7,8,12
startsquare numberings. Here are the 4 with 8 startsquares
that give 8 rows of sum 252 plus 4 startsquares that give 8
columns
of sum 252 :
00,55,08,31,52,43,28,19
07,32,63,54,29,20,51,44
56,01,30,09,42,53,18,27
33,06,57,62,21,26,45,50
02,61,10,37,46,41,22,17
11,34,05,58,25,14,49,40
60,03,36,13,38,47,16,23
35,12,59,04,15,24,39,48
00,43,12,15,52,55,24,35
11,14,63,44,23,36,53,56
42,01,16,13,54,51,34,25
17,10,45,62,37,22,57,50
02,41,06,21,46,61,26,33
09,18,03,38,29,32,49,58
40,05,20,07,60,47,30,27
19,08,39,04,31,28,59,48
00,43,12,15,52,23,56,35
11,14,63,44,55,36,53,24
42,01,16,13,22,51,34,57
17,10,45,62,37,54,25,50
02,41,06,21,46,29,58,33
09,18,03,38,61,32,49,26
40,05,20,07,28,47,30,59
19,08,39,04,31,60,27,48
00,23,08,31,20,43,60,51
07,32,63,22,61,52,19,44
24,01,30,09,42,21,50,59
33,06,25,62,53,58,45,18
02,29,10,37,14,41,54,49
11,34,05,26,57,46,17,40
28,03,36,13,38,15,48,55
35,12,27,04,47,56,39,16
2,10,19,26,34,42,50,58 are the startsquares for the rows in all
4 and
22,30,38,62 , 14,22,30,54 , 14,22,30,54 , 14,38,46,54 for
the columns
----------------
the big files from the 41790 should be split into multiple
volumes
about 1000 additional files) so the process can run on 8 threads
in parallel on a 48GB ramdisk
------------------
the files should be compressed with 7z -mx=3 for faster
decompression, total size will redouble to 6TB
#Post#: 33--------------------------------------------------
Re: SSD with all closed 8x8 knight's tours
By: gsgs Date: January 22, 2024, 11:36 pm
---------------------------------------------------------
the files should be rearranged now for better handling.
I want 550 files with 3e9 tours each.
And also files with the same tours representted
as 168-bit vectors for the used edges.
These are then sorted and another file is made with
the 168-bit vextors of differences of two neighbor-vectors.
A new estimate shows that these 550 difference-files can then
be compressed to about 200 GB in total.
----------edit 2024-01-28--------------
ahh, that estimate was based on a bug.
My actual estimate is 0.8-1.6 TB in total
------------------------------
A fast program to read and convert the difference-vectors to
tours in normal format should be possible.
------------edit 2024-01-28-----------------
I'm also sceptical about that ow.
It may well take >1000 CPU-cycles per tour
on one thread. So to get the tours in
vertex-sequence-format the direct reading of the 3TB
would be faster on a modern computer CPU.
With GPU ... I don't know yet
---------------------------------------------
This process may take some months on one core
and parallelization is not so easy ...
*****************************************************