In the second article I would like to continue the begun subject and to consider a problem of finding of a cyclic route when filling squares of NxN with a course of a horse. But in comments to the first article prompted interesting heuristics, for what to commentators many thanks, and this help, certainly, should be considered in more detail. The idea is known as a rule Varnsdorf and demands to choose first of all from the list of possible courses a course with the smallest number of continuations. It allows at all many times, and to reduce a waiting time of the first decision by orders. Thus additional check on connectivity becomes superfluous, its square complexity only disturbs and slows down process.
the Main recursion described in last article, for compliance to this rule it is simply to change, it is enough to sort the list of possible courses by demanded criterion
of
of knightsTo x [] = [[x]] knightsTo x xs = [x:ks | k Finding of free neighbors should be taken out in the separate
function
of
of neighbors xs x = filter (near x) of xs where near (x1, y1) (x2, y2) = abs ((x2-x1) * (y2-y1)) == 2 Things are easy, it was necessary to paint function of sorting of ksort which orders the list of neighbors in number "neighbors of these neighbors". As option, it it is possible to make so
of ksort xs ns = map snd $ sort $ zip (map (length. ) ns) ns For each neighbor from ns we find (neighbors xs) the list of its possible courses and we calculate its length. Lengths it is packed in couples with coordinates of neighbors. Regular of sort sorts by the first element, i.e. by length then we reject the first elements of couples, leaving only the second.
Is a little florid, but the main thing — result. What there 10x10 — 50x50 is less than in a minute! And even 90x90 if slightly to wait. Here for result 100x100 any more did not wait.
Having experimented with intermediate sizes of squares, it is possible to find out that the algorithm starts stumbling even earlier. The first problem square is 49x49, squares with the parties 64, 76, 87, 89 and 98 go the second 60x60, then. If to begin round of a square not with the left bottom corner, and, say, with opposite, for squares with the parties 49, 60 and 64 solutions are found now, but problems for other squares emerge, and beginning already with the size 23x23. The left top corner allows to find a route in a square 76x76 (and, by the way, 100x100), but problems are found in a square with the party 32. Such selective fastidiousness surprises with
a little and it seems illogical, but also at this rule can arise uncertainty at a course choice. With the identical minimum quantity of outcomes too it is desirable to order neighbors somehow, probably these situations and are critical. But here, really, the more we find answers, the arises questions more. On it a subject with any routes, I think, it is possible to close and pass to routes closed. This task is considered
more difficult, and, really, the requirement to return to an initial cage seems exigeant. After all at creation of the closed route we always have to leave an opening for return. In other words the initial cage has to remain available of the current position on each step of construction. But here again it is worth remembering check of connectivity and the rejected function of connected . Time on an initial cage extends now the same requirement of coherence, as well as of unoccupied cages, it is necessary to add simply it to the general list by each call of function of check. And the initial cage can be transferred to a recursion as one more parameter.
of knFromTo x _ [] = [[x]] knFromTo x s xs = [x:ks | connected [x] (s:xs), k In an amicable way, for a result guarantee, in base of a recursion too it was worth adding check of that the last busy cage connects with initial a course of a horse. But, as any route is unambiguously completed for two courses up to the end, this check is optional to even quantity of cages, and for odd quantity of the closed route all the same does not exist, and for such option the algorithm to the last course will try to close a way, and with the last course for lack of check will simply fill the remained cage.
Slightly we will correct the
interface
of
of knightC n = head. knFromTo (1,1) $ (1,1) delete (1,1) [(x, y) | x I we experiment …
of *Main> knightC 6 [(1,1),(2,3),(1,5),(3,6),(5,5),(6,3),(5,1),(4,3),(3,1),(1,2),(2,4),(1,6),(3,5),(5,6),(6,4),(5,2),(4,4),(6,5),(4,6),(2,5),(1,3),(2,1),(3,3),(1,4),(2,2),(4,1),(6,2),(5,4),(6,6),(4,5),(2,6),(3,4),(4,2),(6,1),(5,3),(3,2)] of *Main> knightC 7 [(1,1),(2,3),(1,5),(2,7),(4,6),(6,7),(7,5),(5,6),(7,7),(6,5),(5,7),(7,6),(6,4),(7,2),(5,1),(6,3),(7,1),(5,2),(3,1),(1,2),(2,4),(1,6),(3,7),(2,5),(1,7),(3,6),(5,5),(4,3),(2,2),(1,4),(3,5),(4,7) a little, (2,6) (3,4),(1,3),(2,1),(4,2),(6,1),(7,3),(5,4),(3,3),(4,1),(6,2),(7,4),(6,6),(4,5),(5,3),(3,2),(4,4)] of *Main> knightC 8 [(1,1),(2,3),(1,5),(2,7), (4,8),(6,7), (8,8),(7,6), (6,8),(8,7),(7,5),(8,3),(7,1),(5,2),(3,1),(1,2),(2,4),(1,6), (2,8),(3,6),(1,7), (3,8),(5,7), (7,8),(8,6),(7,4),(8,2),(6,1),(4,2),(2,1),(1,3),(2,5),(3,3),(1,4),(2,2),(4,1),(6,2),(8,1),(7,3),(5,4),(3,5),(4,3),(5,1),(6,3),(5,5),(4,7),(2,6), (1,8),(3,7),(4,5),(6,6), (5,8),(4,6),(3,4),(5,3),(7,2),(8,4),(6,5),(7,7),(8,5),(6,4),(5,6),(4,4), (3,2) ] For the even sizes of squares (and odd are uninteresting) results are up to the size 50x50, but square complexity of additional check and the last result affects it is necessary to wait 40 minutes.
By the way, it is possible to notice that as an ultimate goal it is optional to specify an initial cage. It is possible to specify any other and the algorithm at creation of a route will diligently aspire to it. To aspire meaning that after filling of all area it will be possible to pass into the specified cage with the following course. It can be used at creation of chains as it was already described in the previous article. Only now, thanks to such purposeful search, the solution will be found much quicker. It is necessary to consider only feature of a course of a horse and to remember that for even quantity of cages the target position has to have the same color of a chess coloring, as initial, in other words, parity of the sum of coordinates has to coincide. And for odd quantity of cages color and, respectively, parity have to alternate.
is A little code and experiments …
As well as in last article we describe function of filling by squares, this time any
size
of
I we apply it to the set
parameters
of
size
of
of knightN n ((m, l) st, fin) = head. knFromTo st fin $ delete st [(x, y) | x I we apply it to the set
parameters
of
of knights10 = concatMap (knightN 5) [((1,1),(5,5),(5,6)), ((1,6),(5,6),(6,6)), ((6,6),(6,6),(6,5)), ((6,1),(6,5),(5,5))] of knights4x26 = concatMap (knightN 26) [((1, 1), (26,26), (1, 27)), ((1, 27), (1, 27), (27,27)), ((27,27),(27,27),(52,26)), ((27, 1),(52,26),(26,26))] knights16x13 = concatMap (knightN 13) [((27,27),(27,27),(27,26)), ((27,14),(27,26),(27,13)), ((27, 1),(27,13),(40,13)), ((40, 1),(40,13),(40,14)), ((40,14),(40,14),(40,27)), ((40,27),(40,27),(40,40)), ((40,40),(40,40),(39,40)), ((27,40),(39,40),(26,40)), ((14,40),(26,40),(13,40)), ((1, 40), (13,40),(13,39)), ((1, 27), (13,39) (13,26)), ((1, 14), (13,26),(13,13)), ((1, 1), (13,13),(14,13)),] the Square 10x10 splitting into four squares 5x5 is filled now ((14, 1),(14,13),(14,14)), ((14,14),(14,14),(14,27)), ((14,27),(14,27),(27,27)) instantly. For a problem square 52x52 filling of the closed chain of four squares 26x26 keeps within 5 minutes of expectation (and in a square 50x50 as it was already spoken, the cycle was looked for 40 minutes). Splitting into 16 squares 13x13 is cyclically filled at all in fifteen seconds. So for the big sizes such method of filling with small areas nevertheless can be useful.
But god with them, with big squares. Finally it would be desirable to touch on one more interesting issue and to try to count quantity of the closed ways (or that to hesitate, Hamilton cycles) in a certain figure column. At least, now it is possible to calculate number of the directed cycles for what it is enough to clean a call of head then function will look for not only the first, but also all possible routes, and to add a call of length to count their quantity. Well and to stock up with patience.
of kNCircles:: Int-> Int-> Int kNCircles m n = ('div' 2) of $ length. knFromTo (1,1) $ (1,1) delete (1,1) [(x, y) | x For odd quantity of cages as we already spoke, such cycles do not exist. For rectangles with a length of one 4 cages they too cannot be constructed of the parties that E. Gika "Mathematics on a chessboard" is proved, for example, in the book. The sizes 5x6 and 3x10 are the smallest among admissible rectangles, and for each of them the program in some minutes finds 16 and 32 options respectively. The rectangle 3x12 contains 352 cyclic routes, 3x14 – 3 072, and for a square of 6x6 such cycles is already 19 724 (thus directed not closed routes from one only a corner it is found in it 524 486 who could think! ) but time for calculation leaves in the afternoon. Exhibitor in all beauty. Big areas and calculations will demand on orders more.
In principle, check of connectivity it is possible to reduce to linear complexity if to find neighbors for constant time. For this purpose, however, it is necessary to complicate structure of data, and, for example, to pass to honest representation of counts in the form of the list of svyaznost. But, first, it would not be desirable to get into a jungle, and, secondly, if to trust an assessment from to Wikipedia , even after all optimization for calculation of quantity of cycles by such rough method on a square 8x8, I am afraid, life will not suffice.
A for wishing to experiment the last practices can be united in one module.
of knights.hs
of import Data.List (delete, (%5C%5C), sort) type Cell = (Int, Int) type Pool = type Track [Cell] = near [Cell]: : Cell-> Cell-> Bool near (x1, y1) (x2, y2) = abs ((x2-x1) * (y2-y1)) == 2 neighbors:: Pool-> Cell-> Pool neighbors xs x = filter (near x) of xs ksort:: Pool-> Pool-> Pool ksort xs ks = map snd $ sort $ zip (map (length. (neighbors xs)) ks) ks knightsTo:: Cell-> Pool-> knightsTo x [Track] [] = [[x]] knightsTo x xs = [x:ks | k Pool-> Bool connected _ [] = True connected [] _ = False connected (x:xs) of ws = let ns = neighbors ws x in connected (xs%2B%2Bns) (ws%5C%5Cns) of knFromTo:: Cell-> Cell-> Pool-> knFromTo x [Track] _ [] = [[x]] knFromTo x a xs = [x:ks | connected [x] of $ a:xs, k Track knights n = head. knightsTo $ (1,1) delete (1,1) [(x, y) | x Track knightC n = head. knFromTo (1,1) $ (1,1) tail [(x, y) | x Int-> Int kNCircles m n = length. knFromTo (1,1) $ (1,1) tail [(x, y) | x Part one