mscroggs.co.uk
mscroggs.co.uk

subscribe

Comment

Comments

Comments in green were written by me. Comments in blue were not written by me.
I decided to write a multi-threaded Partridge solver (in VB.Net) as I have a Xeon E5-2697-v2 12c/24t.

It finds all 18,656 solutions for the '8' puzzle in 2 minutes and all 1,730,280 solutions for the '9' puzzle in 21 hours, which isn't too bad for a 13 year old PC :)

Testing the '8' solver on a single thread took just under 24 minutes (only 12 times 2 minutes, not 24 times), hinting that Hyper-threading memory bandwidth is the bottleneck, so another board storage method is needed to improve the scalability!
Lord Sméagol
on /blog/119
               
@Lord Sméagol: Great job! I guess VB is pretty slow.

The world record in single thread mode for the '8' puzzle is 9.5 min, which can be further improved by taking the diagonal symmetry into account.
You can find the code in the comments to my article: https://habr.com/ru/articles/889410/
Dan
on /blog/119
               
@Dan: I have added symmetry optimization (still in VB.Net):

(Scanning for free space from top to bottom, left to right)
Only place 1x1 in one octant; The tests are simple, the savings are huge.

Even size: 8->36, 11->66, 12->78, 15->120
. . . . . . . . . .
. . . . . . . . . .
. . \ x x x x x . .
. . + \ x x x x . .
. . + + \ x x x . .
. . # # # # # # . .
. . # # # # # # . .
. . # # # # # # . .
. . . . . . . . . .
. . . . . . . . . .

Odd size: 9->45, 10->55, 13->91, 14->105
. . . . . . . . . . .
. . . . . . . . . . .
. . \ x x x x x x . .
. . + \ x x x x x . .
. . + + \ x x x x . .
. . = = = * x x x . .
. . # # # # # # # . .
. . # # # # # # # . .
. . # # # # # # # . .
. . . . . . . . . . .
. . . . . . . . . . .

+ No symmetry check needed
\ Check transpose only
= Check vertical flip only
* Check all 7 symmetries
. 1x1 impossible here
x don't place 1x1 here
# backtrack if 1x1 not placed yet

'8' 2,332 distinct: (12c/24t) 26 sec, (1t) 3m56s

'9' 216,285 distinct: (12c/24t) 3h32m41s, (1t) [32.2 hours estimated]

12c/24t is only getting a 9x improvement over single thread :(
I need to think about making an asm version :)
Lord Sméagol
on /blog/119
×1               
@Lord Sméagol: That's amazing. You've found the way for almost 8x speedup!
Danila P.
on /blog/119
×1               
@Danila P.: I think I have pushed VB.Net to its limit!
I moved the board from byte cells to 64 bit integer bitmaps (1 for each row);
using 8, 9, 10 variables for the 'active' rows instead of an array to reduce memory access.

I also partitioned the '9' and '10' search so other computers (I have a 6c/12t i7 3930K and a few quad cores) can assist using a mapped network drive.

All 2,332 distinct solutions of the '8' puzzle (12c/24t) now 16 secs (was 26 sec).

I have ported most of it to C ... just need to get the multi-threading working!
Lord Sméagol
on /blog/119
               
@Dan: 9.5 min on what CPU, RAM ? My rig is 3.5 GHz single thread Ivy Bridge, DDR3 1600, which will be holding me back quite a lot compared to modern kit!

The main problem with VB.Net (well, .Net itself) is only allowing you to disable integer overflow checks.
I remember VB6 let you also disable array bounds checking. That option SHOULD be available in .Net!
--> Test your code in Debug mode ... ok, it works, release mode with no checking --> let it rip!

My VB.Net prog spits out solutions as it finds them, but this hardly impacts performance. There is a single render thread that waits for a solution from a shared queue that [24 in my case] worker threads are feeding.

I would like to keep all the hot stuff in registers, but I don't think C will give me enough control over that, so maybe it's asm time!
Lord Sméagol
on /blog/119
         ×1      

Archive

Show me a random blog post
 2026 

May 2026

World Cup stickers 2026

Apr 2026

A new puzzle every day
Mixing Wordle with other games

Feb 2026

Christmas (2025) is over
 2025 

Dec 2025

Christmas card 2025

Nov 2025

Christmas (2025) is coming!

Sep 2025

The partridge puzzle

Aug 2025

TMiP 2025 puzzle hunt

Jun 2025

A nonogram alphabet

Mar 2025

How to write a crossnumber

Jan 2025

Christmas (2024) is over
Friendly squares
 2024 

Dec 2024

A regular expression Christmas puzzle
Christmas card 2024

Nov 2024

Christmas (2024) is coming!

Feb 2024

Zines, pt. 2

Jan 2024

Christmas (2023) is over
 2023 
▼ show ▼
 2022 
▼ show ▼
 2021 
▼ show ▼
 2020 
▼ show ▼
 2019 
▼ show ▼
 2018 
▼ show ▼
 2017 
▼ show ▼
 2016 
▼ show ▼
 2015 
▼ show ▼
 2014 
▼ show ▼
 2013 
▼ show ▼
 2012 
▼ show ▼

Tags

oeis numbers gaussian elimination advent calendar guest posts flexagons quadrilaterals game show probability matt parker pokémon wordle stickers fonts dataset live stream christmas python databet sorting matrix multiplication mean sound radio 4 weak imposition dinosaurs bempp royal baby noughts and crosses palindromes wool stirling numbers kings menace video games platonic solids coins frobel accuracy pokémon preconditioning friendly squares thirteen rust boundary element methods fence posts world cup latex fractals manchester electromagnetic field christmas card football computational complexity pi approximation day kenilworth finite group curvature crosswords cross stitch bluesky news dragon curves royal institution crossnumber big internet math-off chebyshev pac-man puzzles squares wave scattering warwick approximation inline code pythagoras captain scarlet binary london underground edinburgh matrix of cofactors alphabets plastic ratio turtles interpolation light data visualisation a gamut of games manchester science festival phd correlation martin gardner mathsteroids php hannah fry london braiding hexapawn final fantasy numerical analysis european cup javascript estimation zines graphs probability data reddit misleading statistics pascal's triangle sport bubble bobble coventry nonograms pizza cutting geometry nine men's morris folding tube maps asteroids newcastle chess arrangement puzzles wordle convergence sobolev spaces mathsjam hyperbolic surfaces game of life mathslogicbot tmip finite element method craft runge's phenomenon ucl hats 24 hour maths reuleaux polygons bots error bars statistics rhombicuboctahedron datasaurus dozen weather station polynomials raspberry pi exponential growth errors harriss spiral machine learning pi standard deviation golden ratio programming chalkdust magazine logic matrix of minors signorini conditions propositional calculus go countdown games triangles inverse matrices regular expressions ternary anscombe's quartet bodmas cambridge golden spiral arithmetic tennis logs crochet crossnumbers youtube realhats recursion draughts trigonometry national lottery talking maths in public people maths geogebra tetris rugby graph theory dates gerry anderson the aperiodical logo partridge puzzle simultaneous equations books folding paper determinants matrices gather town map projections speed

Archive

Show me a random blog post
▼ show ▼
© Matthew Scroggs 2012–2026