mscroggs.co.uk
mscroggs.co.uk

subscribe

Comment

Comments

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

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

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

Archive

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