mscroggs.co.uk
mscroggs.co.uk

subscribe

Comment

Comments

Comments in green were written by me. Comments in blue were not written by me.
@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

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

Archive

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