Brute-force pathfinder

[devout sundial]

This is my first C++ project. It started in search of an answer for this question that I asked on stackexchange: https://math.stackexchange.com/q/5036847,
what is the shortest path that touches every square in a square grid?

Regardless of what the answer is, we can keep going and brute-force ALL paths for even larger n.
I'd like to hear about everything that I am doing wrong, github stuff included, any concrete ideas about better algorithms that could work. I am not afraid of a complete rewrite, my only goal is finding more solutions. Feel free to contribute if the problem interests you.
https://github.com/tomka700/Minimal-path

[tired heath]

It's cool that the brute force solutions looks like what you'd expect from an optimal space filling curve

[devout sundial]

that's one of the many reasons why the orthogonal only case is trivial, I mention it at the bottom of the stackexchange post

[devout sundial]

I think this is such a cool problem that deserves more attention but a lot of people seem to go "damn that's cool" and then move on. Could I do a better job of drawing them in?

[tired heath]

Not sure 🙂

It's a cool problem, and the diagram is pretty. I might take a stab at it tomorrow.

[devout sundial]

that's great to hear man ty

[tired heath]

I wanted to play around with using z3 to solve this but even for a 3x3 the solver is taking forever

The constraints here can probably be optimized but I'm surprised it's taking as long as it is

Unfortunately z3.Optimize doesn't support square roots so I'm having to use a workaround

[tired heath]

yeah, I think z3 might not be very well optimized for these sorts of problems

in fairness they're tricky

[devout sundial]

I am not familiar with that

I have thought of two simple ways this problem could be sped up, I just lack the expertise for both: using the GPU and converting it all to a single graph

[devout sundial]

oh is it a computer-assisted proof kinda thing

[devout sundial]

maybe I am misunderstanding but can we not use the current best formulas for minimal length to cut down on this somehow

this also might be useful, a union of all symmetries of all proven (until n=10) and current best (n>10) solutions

[tired heath]

Cool 🙂

Surprisingly pretty

[devout sundial]

that's the distraction heh, the main things to notice are the lack of diagonals to corners and the lack of parallel to the edge lines at y=2 (and its symmetries ofc)

[tired heath]

indeed

[devout sundial]

z3 looks like haskell, I'll try to put something together with it

not quite sure I understand which part of it is responsible for the touching touching squares logic though

[devout sundial]

we can avoid square roots by using chebyshev distance (if we only check for moves of chebyshev length 1) for every case except for 3 as there you get false positives like the picture as it is also the only case where not every move is optimal in the amount of new squares it visits per move, I edited the readme just now to include that

and then I assume we can use a count() instead, for which we know the upper bounds as described in the stackexchange post

[devout sundial]

@shrewd parcel

[shrewd parcel]

ah, here

[devout sundial]

this has more visual context for deeper understanding

[shrewd parcel]

so yeah, definetly try the thread-pool first. Should probably save you like 5-10 seconds of your 45 second runtime, whereas for my 21 seconds it'd probably be saving like 3-5 seconds

[devout sundial]

you might find something in the stackexchange link

maybe this can be a useful reframing?

[tranquil isle]

instead of using bitset, why not use uint64?

you're only using 8 * 8 bits.

i suppose n can be changed? can't tell from a quick look since its constexpr

[devout sundial]

that's an example n, the next n to tackle is 11

[tranquil isle]

i see, got it.

[devout sundial]

and no reason to not use bitset from what I can tell

[tranquil isle]

also, you should avoid vectors..

there's no need for them if you have a fixed n

they're considerably slowing down your code because heap allocations aren't cheap

and there's a lot of copying happening as well .. for resize purposes

yeah everywhere you used a vector, an array can be used instead.

[devout sundial]

the length of the paths isn't proven, we only have an upper bound, they should be reserved for and locally copied inside of search_from
paths definitely has to be a vector but that isn't relevant per the above point

[tranquil isle]

upper bound means u can preallocate it

and then keep track of size

path definitely won't exceed n * n nodes

[devout sundial]

doesn't reserve preallocate?

[tranquil isle]

it still heap allocates

[devout sundial]

CURRENT_BEST

ah

on the todo it goes

[tranquil isle]

a lot of stuff can also be SIMD for maximum performance

it isn't truly obvious to the compiler so my guess is it isn't doing that rn

other than that, focus on cache locality

and yeah, that's best you can do rlly

[devout sundial]

I'm not familiar with simd

[tranquil isle]

as in, have never used it but know about it or have no clue what that is?

[devout sundial]

I have heard simdeez nuts before

that's where my knowledge ends

This is my first C++ project.

[tranquil isle]

ah, i see

this video explains it well, i suggest you to watch: https://youtu.be/ulmjqD6Y4do?si=Hpvn1-fJj5o0d_OG

a raytracer goes from taking 31 minutes to just 49 seconds.

that's what SIMD can do.

[devout sundial]

unsure how that can be applied here, I get that the inside of dfs is the same but they branch in different directions, does that matter?

[tranquil isle]

so for example, there exists simd instructions for masking

any algorithm can be converted into an operation on vectors

[devout sundial]

do I need to change my multithreading implementation to use that

[tranquil isle]

multi-threading may not even be needed if you get simd working

at least for small n .. say less than 1024

[devout sundial]

we are not getting to 1024, 10 takes days

[tranquil isle]

yeah, then if you can get simd working for you, that'll really speed up your stuff.

[devout sundial]

9 is ~43s, it is highly exponential

[tranquil isle]

ofc, that's how tree search is

[devout sundial]

c^(n^2) where 3 < c < 8

[tranquil isle]

yeah i mean, SIMD works best for brute force.

if you have a lot of branching in your code, SIMD isn't for that unless you translate to non-branched vector version.

[devout sundial]

brute-force is used loosely here, it only means that we want to find all paths for any given n