over the last few weeks I've been hunting for knights tours that satisfy a specific property. In fact, I'm trying to find *every* tour that satisfies the property.

strangely, I've ended up using math that is normally used in ecology

so, I've written two very different programs for finding these tours. One is a simple backtracking search: you move the knight across the board, and the moment the knight can't go anywhere or the desired property is violated, you undo your move and try somewhere else

the second uses the cryptominisat library, which is a more generalist problem solving library where you pose your problem as a set of constraints on a set of binary variables, then the library tries to find assignments of those variables that satisfy your constraints.

the second program represents the board as a 64x64x64 array of variables, where a var at (x,y,z) is true iff the knight visited the square (x,y) at time z. I add constraints to ensure the vars encode a knights tour, then add more so it's only generating tours I'm interested in

anyway, I've given both quite a lot of CPU time, and now I'm wondering, how many of my special knights tours are left to find?

and I realized, I can use mark and recapture math!

"mark and recapture" is a technique used in ecology to estimate the population of some species in the wild. generally, it's not possible to count every single animal individually, so this statistical technique is used

the gist is: you capture, say, 100 animals and add a harmless mark or tag to them so you can identify them in the future. then sometime in the future, you capture another 100 animals from the same population.

in the 100 animals you captured the second time, some of them may have the mark from the first set of captures. if you assume that both sets of captures are statistically independent, you can use the number of overlapping animals to estimate the true size of the wild population

matt parker did a pretty good video about the math behind this technique, if you want a better explination: youtube.com/watch?v=MTmnVBJ9gC

ok, back to knights tours.

if I assume that my programs are generating these tours statistically independently of each other, I can use this same mark and recapture math to estimate the total population of my special tours

given that they work in fairly different ways (ok I know SAT solvers are kinda like backtracking algorithms, but let me have this) I feel ok believing they are independent.

ok now for the actual numbers:

both of my programs generated 154 tours with my special property. and there were 59 tours that were generated by both of them.

plugging them into this website: epitools.ausvet.com.au/capreca

I get that the most likely total amount of my knights tours is 399 (with 95% confidence that it's between 338 and 461)

so why do all this? well part of it is curiosity, but also I want to know if it's even worth my time to find all of these tours. If I did all this and there was only 1 tour common between the two programs, this would mean the true total is more like 12012

given that it took a week or so to find 249 tours, this would mean it would take months to find them all. and I would probably give up at that point.

anyway, that's the end of the thread, thanks for reading!

eratta: I realized I said "64x64x64 array of variables, where a var at (x,y,z) is true iff the knight visited the square (x,y) at time z"

I meant 8x8x64, since a chess board is 8x8 not 64x64


errata: I misspelled "errata" as "eratta"

· · Web · 0 · 2 · 11
Sign in to participate in the conversation

cybrespace: the social hub of the information superhighway jack in to the mastodon fediverse today and surf the dataflow through our cybrepunk, slightly glitchy web portal support us on patreon or liberapay!