Linksback to main page "WorldRecord".. Other languages |
Next goals: Q28 and T35On the way to world record Q28 in JapanIn Japan, ateam (Yuuma Azuma, Hayato Sakagami, Kenji Kise of the Tokyo Institute of Technology) started for the next mile stone; see this article. One of the team, Kenji Kise, has corrected the wrong number for Q24, back in 2004, if I am not mislead by a contigous equality of the name. Dr.Thomas Preußer informed me in the end of 2018, saying that the descripted method is quite feasible; meanwhile, more than a year has gone - I am curious about it! On their page, I could not find an information about it. On the Torus side: T35For a considerable time I am working to find out the number for T35. My approximation formula (see article "An Easy Counting Lemma") gives a value of 9.66 quadrillions; on 7th of march, 2020, the number of 53,742,116,622,600 (ca 54 trillions) were definitely found, corresponding to 0.55 percent only of the estimated value. General approachThe general approach is described in the paper How to search Torus N Queens solutions. Shortly and without further explanations I write it down here. The approach consists of the following points:
The search needs much computing effort; the project is supported by Lino GmbH, which provides a virtual server, for the time not used from other application. For the rest, my computer is working on it, and it may take still a couple of years. The search is running in the background and affects other activities very little. It is easy to interrupt the search if needed and resume it later. Chronology
Special points, which I detected during the searchHow to handle the skeletons?The way for an efficient search was planned via the skeletons with respect to necklaces - of course skeletons and necklaces as mathematical terms. I also thought that a big part of the search could be done on FPGAs. Unfortunately, this is too complex for an efficient implementation on FPGAs. Therefore, the program is executed on conventional Intel-compatible PCs completely. Meanwhile, I am thinking of another idea in parallel: do the search with line skeletons instead of necklace skeletons; I will explain it further in the future. Roughly speaking, necklace skeletons handle lines containing many queens in a predefined order; for line skeletons, the order of the queens does not matter, only the number of queens on the lines is of interest. To find the necklace skeleton of a solution requires relatively much CPU; but perhaps I must only optimise my implementation. A different approach is to search the line skeleton first, and from it the necklace skeleton afterwards. Up to now, the search for the line skeleton is faster by a considerable factor: for T23, the factor is 244, for T25 it is 324. The disadvantage is that there are more line skeletons than necklace skeletons. To get some impression of the numbers, I have generated diagrams showing the number of solutions, depending on the size of the skeleton, both for line and necklace skeletons. Distribution, depending on the size of the skeleton.
The first solutions for "large" cases.During the search from 3 preset queens only, the solutions below were found among others, in the first 130 hours, on the server of Lino GmbH:They belong to necklace 6, with beads at 0-1-3; this gives preset queens on 0/0, 2/1, and 6/3. Queens of the skeleton are marked with a black plus sign. Some colored lines show further knight lines populated with three queens in a position corresponding to the necklace. For example in the left image the queens on 17/5, 19/9, and 23/17 (bright green line). In this case, the necklace is expanded to 0-2-6 (by factor 2). One can see also the three queens on 8/13, 10/14, and 12/15 on a knight line; but these positions belong to the smaller necklace 0-1-2, therefore the queens do not belong to the skeleton. |