[sizediterable]

I also wrote my solution in Rust. I was pleased that my approach gave me an opportunity to write a linked list and get the chance to apply some rarely used learning[0].

My solution doesn't use SIMD, but is actually takes about the same amount of time as the the solution in the article, given the same number of cores, though an glaring weakness of my approach is that it can only scale up to 7 cores as written.

Rough outline of how mine works:

- Set current best GCD to 1.

- Search through all valid board configurations.

- Bail out from the search early if the current partially generated board couldn't have a GCD greater than the current maximum found, e.g. if we've only generated two rows of the board, and the GCD of those two rows are already less than the max.

- Update the current best GCD as you find higher ones.

- Share the current best GCD value across multiple threads. That way the longer the program runs, the earlier and earlier the searches will start bailing out.

- Don't always read from the shared variable to avoid contention. Instead, each thread has its own copy of the last value it read which we compare with first before copying and caching the shared value.

- Another interesting property of this approach is that it can be used to validate the correct solution even faster than it takes to find it. Instead of initially setting the max GCD to 1, set it to `solution - 1`. That way branches in our search will bail even sooner from the beginning. This leads to the program running about 20% more quickly.

Source: https://gist.github.com/lazytype/35b45f3ea81b5c1c5555546fe6f...

[0] https://rust-unofficial.github.io/too-many-lists/