Blog
2026-04-20
This is an article that I wrote for
Chalkdust issue 23, and the
new puzzle it introduces appears on the cover of issue 23.
In January, I paid a visit to MathsWorld, the recently opened maths discovery centre
in London, alongside some other members of the Chalkdust team.
One of the highlights of the trip was playing the two-player game Genius Square.
In Genius Square, you start with a six-by-six board and roll seven dice. These dice tell you where
to place seven cylindrical blocks, for example:
![](javascript:showlimage("genius-square-dice.png"))
The dice
![](javascript:showlimage("genius-square-board.png"))
![](javascript:showlimage("genius-square-pieces.png"))
The board with the cylinders placed and the pieces
The two players then race to fit the pieces shown above into the remaining space on the
board. The pieces that the players have are
the five tetrominoes,
the two triominoes,
a domino,
and a single square (or monomino); these are all the shapes you can
make by gluing together up to four squares (if rotations and reflections are considered the same
shape).
If you want to ruin/improve your copy of Chalkdust, you could cut out the pieces shown above and
try to fit them in the board to the left.
There's some clever design in this game:
if, instead of rolling the dice, you were to randomly pick any set of seven spaces to place the cylinders,
the puzzle is not guaranteed to have a solution.
The locations printed on the dice have been carefully chosen so that any combination that you can roll
leads to a solvable puzzle.
A puzzle-a-day
The Genius Square puzzle is similar to another rearrangement puzzle: the puzzle-a-day calendar,
created by the Norwegian puzzle makers DragonFjord.
![](javascript:showlimage("puzzle-a-day-board.png"))
![](javascript:showlimage("puzzle-a-day-pieces.png"))
The puzzle-a-day board and pieces
In this puzzle, you are given the pieces below
and asked to place them on the board to cover everything except
today's date. For example, on 22 July, you could place the pieces like this:
![](javascript:showlimage("puzzle-a-day-22-july.png"))
A solution of puzzle-a-day for 22 July
DragonFjord make and sell wooden and plastic versions of puzzle-a-day, which
you can buy from Maths Gear—who
also provide the top prize for the crossnumber—to
avoid the cost of shipping directly from Norway.
In puzzle-a-day, it's possible to arrange the pieces to make every single combination
of a number and a month, including days that don't exist like 31 September and 30 February.
![](javascript:showlimage("puzzle-a-day-31-september.png"))
A solution of puzzle-a-day for 31 September?!
While we were considering options for the cover of this issue, we discussed putting something
like Genius Square on the cover, and I began to wonder
if it would be possible to make
a puzzle like puzzle-a-day but where it was only possible to make days that actually appear on the
calendar.
A new puzzle
After spending a while scribbling on squared paper and getting nowhere,
I had an idea: I could put the months in regions that were disconnected from the day numbers. Then,
by carefully choosing the shape of the month regions and the arrangement of the dates, I could force
the solver to use different combinations of pieces on the day numbers for different months.
Once I'd had this idea, I threw together some Python code that could see which day numbers
you could and couldn't leave uncovered with a set of pieces, and waited for it to find a good
set of pieces. It found this board and these pieces:
![](javascript:showlimage("new-puzzle-a-day-board.png"))
![](javascript:showlimage("new-puzzle-a-day-pieces.png"))
The board and pieces for the new puzzle
As in Tetris, I've named the pieces after letters that they vaguely resemble.
In January, March, May, July, August, October and December, you have to use
a P, an O and the A in the month regions.
The remaining pieces can make any day from 1 to 31.
In April, June, September and November, you need to use the C, an O and the A in the month regions.
This leaves pieces that can make any day from 1 to 30, but importantly can't make 31.
In February, you need to use both Os and the C in the month regions.
This leaves pieces that can make any day from 1 to 29, but not 30 or 31.
Now all we need to do is find another new arrangement that somehow works differently in leap and non-leap years...
×1 ×1 (Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
Add a Comment
2026-02-08
Welcome to 2026 everyone! It's time to reveal the answers to the Advent Calendar puzzles and announce the winners.
But first, some good news: with your help, Santa was able to order a new sleigh and Christmas was saved!
Now that the competition is over, the questions and all the answers can be found at mscroggs.co.uk/puzzles/advent2025.
Before announcing the winners, I'm going to go through some of my favourite puzzles from the calendar and a couple of other interesting bits and pieces.
Highlights
My first highlight is the puzzle from 9 December. I like this puzzle, and enjoy how it looks
like a complicated counting puzzle at first, but there's a much simpler method available...
9 December
In a 3 by 5 grid of squares, if a line is drawn from the bottom left corner to the top right corner, it will pass through 7 squares:
![](javascript:showlimage("advent2025-squares.png"))
In a 251 by 272 grid of squares, how many squares will a line drawn from the bottom left corner to the top right corner pass through?
My next highlight is the puzzle on 17 December. This is a highlight because I just really like the puzzle.
17 December
A sequence of zeros and ones can be reduced by writing a 0 or 1 under each pair of numbers: 1 is written if the numbers are the same, 0 is written if they are not.
This process can be repeated until there is a single number. For example, if we start with the sequence 1, 1, 1, 0, 1 (of length 5), we get:
1
1
1
0
1
1
1
0
0
1
0
1
0
0
1
The final digit is a 1.
How many sequences of zeros and ones of length 10 are there that when reduced lead to the final digit being a 1?
My final highlight is the puzzle from 18 December, as I always enjoy a surprise Fibonacci.
18 December
There are 5 different ways to make a set of numbers between 1 and 5 such that the smallest number in the set is equal to the number of numbers in the set. These 5 sets are: {1}, {2, 3}, {2, 4}, {2, 5} and {3, 4, 5}.
How many ways are there to make a set of numbers between 1 and 14 such that the smallest number in the set is equal to the number of numbers in the set?
Hardest and easiest puzzles
Once you've entered 24 answers, the calendar checks these and tells you how many are correct. I logged the answers that were sent
for checking and have looked at these to see which puzzles were the most and least commonly incorrect. The bar chart below shows the total number
of incorrect attempts at each question.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| Day | |||||||||||||||||||||||
It looks like the hardest puzzles were on
21,
15 and
14 December;
and the easiest puzzles were on
3,
10,
5 and
8 December.
Ordering the sleigh
To finish the Advent calendar, you were tasked with ordering the correct parts for a new sleigh. The answers to all the puzzles were required to
be certain of which combination of parts was needed, but it was possible to reduce the number of options
This graph shows how many people successfully ordered a sleigh on each day:
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| Day | ||||||||||
The winners
And finally (and maybe most importantly), on to the winners: 242 people managed to order a slieigh. That's a record high number!
| 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | 2021 | 2022 | 2023 | 2024 | 2025 |
| Year | ||||||||||
From the correct answers, the following 10 winners were selected:
- Adrienne Hestenes
- Blake Segler
- Johannes C. Huber
- Matthew Harding
- Mr J Winfield
- Pamela Docherty
- Pete Chare
- Steve Blay
- Tim Dufton
- Vinny R
Congratulations! Your prizes will be on their way shortly.
The prizes this year include 2025 Advent calendar T-shirts. If you didn't win one, but would like one of these, I've made them available to buy at merch.mscroggs.co.uk alongside the T-shirts from previous years.
Additionally, well done to
100118220919SantaSixSeven9, A Hall, Aaron Kunze, Aisha Arroyo, Alan Buck, Alan Shotkin, alek2ander, Alex Bolton, Alex Slaughter, Allan Taylor, Anastasia P, Anastasiia, Andrea Chlebikova, Andrew Brady, Andrew Fermor, Andrew Roy, Andrew T, Andrew Thomson, Andy Ennaco, Artie Smith, Ashley Jarvis, B Witt, Becky Russell, beeplusdub, Ben Baker, Ben Boxall, Ben J, Ben Reiniger, Ben Semanko, Ben Tozer, Ben Weiss, Bill, Bill Russ, Bob B, Brian Wellington, Carmen, Cathy Hooper, Chad Smith, Chloe, Chris Dettmar, Chris Eagle, Chris Hazell, Chris Hellings, Christopher Adams, Clint Cabrera, Colin Beveridge , Colin Brockley, Connie, Cool Beans, Corbin Groothuis, Cristian Sbârciog, dajedrek, Dan Colestock, Dan May, Dan Whitman, Daniel, Daniel Low, Danny, Dave, Dave Budd, David, David Ault, David Berardo, David Carey, David Fox, David Kendel, Deborah Tayler, Dhruv Pisharody, Donagh, Donald Anderson, Dylan, Dylan Madisetti, Echo231, Elijah Kuhn, Elizabeth Madisetti, Ellie Winters, Elytre, Emily Troyer, Eoin Davey, epsilon, Eric Kolbusz, Erick Lee, Evan and Dana, Evan Denney, Evan S, Ewan Beetham, F Z, Fabien Friedli, Fionn Woodcock, Frank Kasell, Fred Verheul, Gabriella , Gareth McCaughan, Gary M. Gerken, Gary Male, Gert-Jan, Gregory Wheeler, Guillermo Heras Prieto, H.Hung, Hannah Harris, Heerpal, Helen, Herschel, Holly Carnes, Håkon Balteskard, IanAllenBird, Iris Lasthofer, Isabel Turner, Ivan Andrus, Jacob, Jamas Enright, James Chapman, James Dolengewicz, James Swenson, Jan Zemba, Jay Winter, JDev, Jean-Noël Monette, Jen Sparks, Jessica Marsh, Joe Gage, Johan, Jon Palin, Jonathan Chaffer, Jonathan Thiele, Jorge del Castillo Tierz, Josh Hernandez, Judith W, Kat, Kat Yates, Katerina Stergiopoulou, Katie Steckles, Keerthana, Kevin Docherty, Kirsty Fish, Kristen Koenigs, Larry Goddard, lastrun, Lazar Ilic, LDufton, Leif Cooper, Lewis Dyer, Lisa Stambaugh, Lise Andreasen, Lizzie McLean, Lorelei, Louis, Lucas Bowman, Magnus Eklund, Mair A-W, Marc G., Marco van der Park, Mark Lydon, Mark Stambaugh, Martin Harris, María Jesús Rapanague, mathmandan, Matthew Courtney, Matthew Schulz, Max, Maya, Michael, Mihai Zsisku, Mike Graczyk, Millie, Mimi Manning, Mister Ron, Monopoler, Nazneen Molu, Neil Bastian, Nick C, Nick Keith, Nikos I., Noah Molder, Noah O, Oli M, Olov, Pablo Carballeira, Peter Krol, Peter Rowlett, Pierce R, Pollyanna, Pythialouise, Rachel Sheridan, RADina, Rashi, Ray Arndorfer, Richard O, Rob Reynolds, Robert, Robert Allwright, Roger, Roni, Ronno, Rosamund, Rosie Paterson, Sadie Robinson, Sam Dreilinger, Sam Peterson, Sam123guy, Samuel Wilson , Scio Durango, Scott, Sean Henderson, Seth Cohen, Shannon Stranahan, Shivanshi, Simon English, sjlxndr, stephen kirkham, Stephen Royle, Tamas Toth, Tarka Burrell, Tehnuka, The Connors of York, Thomas O'Neill, Tim B, Timothy Conlan, Tina Furer, Tino, Tony Mann, Travis, tripleboleo, UsrBinPRL, Valentin VĂLCIU, Victor MIller, Vinayak, Will Bayliff, Willem, Yasha, and zook
who all also completed the Advent calendar but were too unlucky to win prizes this time or chose to not enter the prize draw.
See you all next December, when the Advent calendar will return.
×6 ×2 (Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
Yes I did puzzle 9 by working out how many would be coloured in each row or something, and only realised that there was a simpler way when I saw the final formula. Cheers pal
Alex Bolton
Add a Comment
2025-12-04
As usual, I spent some time this November,
designing this year's Chalkdust puzzle Christmas card
(with help from TD and Jacob).
![](javascript:showlimage("card2025.jpg"))
The card contains 12 puzzles: 8 in the green section, and 4 in the red or yellow section. By colouring the two squares on the front of the card containing every pair of digits in each answer
(eg if an answer in the green section were 3305, you would colour the squares containing 33, 30 and 05 green), you will reveal a Christmas
themed picture.
If you're in the UK and want some copies of the card to send to your maths-loving friends, you can order them from my Ko-Fi shop.
If you want to try the card yourself, you can download this printable A4 pdf. Alternatively, you can find the puzzles below and type the answers in the boxes. The answers will automatically be used to colour in the appropriate squares.
Green | ||
| 1. | What is the sum of all the odd integers between 0 and 12? | Answer |
| 2. | What is the sum of all the odd integers between 0 and 44444? | Answer |
| 3. | Carol has more than one bauble. When she shares them equally between 3 people, there is one bauble left over. When she shares them equally between 4 people, there is still one bauble left over. What is the smallest number of baubles that Carol could have? | Answer |
| 4. | Carol has more than one bauble. When she shares them equally between 2, 3, 4, 5, 6, 7, 8, or 9 people, there is one bauble left over. What is the smallest number of baubles that Carol could have? | Answer |
| 5. | What is the smallest three-digit positive integer whose digits are all non-zero and different? | Answer |
| 6. | How many positive integers are there whose digits are all non-zero and different? | Answer |
| 7. | In a Christmas game, you can win either 4 points or 5 points on your turn, and the game can last any number of turns. What is the largest number of points that it is impossible to end the game on? | Answer |
| 8. | In a different Christmas game, you can win either 495371 points or 2921695 points on your turn, and the game can last any number of turns. What is the largest number of points that it is impossible to end the game on? | Answer |
Red or yellow | ||
| 9. | What is the smallest two-digit positive integer that cannot be written as the sum of consecutive integers? | Answer |
| 10. | What is the smallest four-digit positive integer that can be written as the sum of exactly four consecutive integers? | Answer |
| 11. | Holly drew 18 points on the circumference of a circle then drew straight lines connecting each pair of points. How many straight lines did she draw? | Answer |
| 12. | Holly drew some points on the circumference of a circle then drew straight lines connecting each pair of points. She drew 166047976 straight lines. How many points did she draw? | Answer |
×13 ×3 ×1 ×1 ×4(Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
Will you be posting solutions? I have what is to me an acceptable answer but I think I might be missing a couple of squares
Ewan Leeming
Thanks again for an advent full of brain teasers. Merry Christmas!×2
Gert-Jan
×2 Add a Comment
2025-11-20
The mscroggs.co.uk Advent Calendar is back for its eleventh year, making it the Advent calendar's tenth anniversary!
Behind each door, there will be a puzzle with a three digit solution. The solution to each day's puzzle forms part of a logic puzzle:
It's nearly Christmas and something terrible has happened: after years of gradual wear and tear, Santa's magic sleigh has fallen apart.
You need to help Santa build a new sleigh so that he can deliver presents before Christmas is ruined for everyone.
The magic sleigh was built from parts bought from magic factories all over the world, and only the exact combination of parts will be magic enough to let Santa deliver all
the world's presents on Christmas Eve—but it's been a long time since a magic sleigh was last built and no-one can remember exactly which combination of parts is needed.
Behind the first 24 doors on the Advent calendar, there are puzzles with three-digit answers. Each of these answers forms part of piece of information about the sleigh that
Santa and his elves can remember: you need to use this information to work out which runners, chassis, present holder, seat for Santa, and front of the sleigh with reins
you need to order from the nine suppliers (numbered from 1 to 9) that Santa can order parts from.
You can use this page to try ordering parts for a sleigh, but you can only try ordering three times per day (or Santa's suppliers will get
very angry about cancelled orders).
Ten randomly selected people who solve all the puzzles, build a magic sleigh, and fill in the entry form behind the door on the 25th will win prizes!
![](javascript:showlimage("prizes2018.jpg"))
The prizes will include an mscroggs.co.uk Advent 2025 T-shirt. If you'd like one of the T-shirts from a previous Advent, they are available to order at merch.mscroggs.co.uk.
The winners will be randomly chosen from all those who submit the entry form before the end of 2025. Each day's puzzle (and the entry form on Christmas Day) will be available from 5:00am GMT. But as the winners will be selected randomly,
there's no need to get up at 5am on Christmas Day to enter!
As you solve the puzzles, your answers will be stored. To share your stored answers between multiple devices, enter your email address below the calendar and you will be emailed a magic link to visit on your other devices.
To win a prize, you must submit your entry before the end of 2025. Only one entry will be accepted per person. If you have any questions, ask them in the comments below,
on Bluesky,
or on Mastodon.
If you'd like to chat with other solvers, we'll be discussing the Advent Calendar in the #scroggs-advent-calendar channel in the Finite Group Discord: you
can join the Discord by following the link in this post on Patreon (you'll need to become a free member
on Patreon to unlock the post).
So once December is here, get solving! Good luck and have a very merry Christmas!
×10 ×7 ×3 ×3 ×3(Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
Thank You for the notification of this year's bounty from yourself.
Wish you a Merry Xmas and a Wonderful New Year !!!×3 ×2 ×2 ×2
Wish you a Merry Xmas and a Wonderful New Year !!!
Jim
×3 ×2 ×2 ×2 @Artie: Yes, I will be. A cold wiped out the bit of the year between new year and going back to work so it's later than usual but it will be done soon.×1 ×2
Matthew
×1 ×2 You usually post a list of successful entries - will you be doing so this year (or can I just not find it). I have gotten a number of my students into doing this each year and I am keen to see if any are still doing it.
Artie
I am so excited to share with you my greatest testimony how Dr Marcus made me achieve my dreams after 10 years of playing the lottery. I saw a couple of comments about him several years ago. I wondered how it was possible. Until it finally works for me the numbers he gave me were what I played, I'm still in shock. I, a Lapeer county man, won the $1,000,000 power ball, the only word I can use to describe the feelings of finding out that I have won the 1 million dollars is shocking. I am just now believing that this is real. Dr Marcus is indeed a powerful man. You can reach him at drmacusspellcaster@gmail.com or whatsapp him at +234 811 049 2028
robert benaglio
I couldn't figure out a rule for 21/14 so I decided to count it, realized that I had only gotten 1/8 of the way through with the counting in 5 days, so I took the result at the time, multiplied it by 4, then brute forced it down. I figured one out after though. Good puzzles \|
Durango Koval
Great year-end fun as usual! Will there be some kind of annotated solutions afterwards? Also hoping to use this space to discuss the solutions after the competition is closed. Especially interested in the neat solutions for 14 and 21 that some commenters alluded to. If allowed, would also like to share some insights for 9 which many seemed to struggle with (brute force not needed!) after the competition closes.
H.Hung
Add a Comment
2025-09-06
Recently, Matt Parker released a video about a puzzle related to the year 2025:
due to 2025 being the square of a triangle number, the following fact is true:
$$
1^3+2^3+3^3+4^3+5^3+6^3+7^3+8^3+9^3
=
(1+2+3+4+5+6+7+8+9)^2
= 2025.
$$
This fact can be rexpressed as: the total area of
one 1×1 square, two 2×2 squares, three 3×3 squares and so on up to nine 9×9 squares
is the same as the area of a 45 by 45 square. This leads to a question: is it possible to arrange this large collection of squares to make the larger square?
The general form of this puzzle (where we sum to \(n\) rather than to 9) is called the partridge puzzle. It was named this by Robert Wainwright
as the version with \(n=12\) reminded him of the total number of gifts in the 12 days of Christmas (although this link isn't exact as the total number of gifts is
12×1 + 11×2 + 10×3 + ... + 1×12 rather than the sum of the cubes).
For Matt's video, I made an interactive tool that lets you arrange the pieces and attempt to solve the problem: you can play with it at mscroggs.co.uk/squares.
How many solutions?
When \(n=1\), the question becomes the very boring "can you arrange a 1×1 square to make a 1×1 square?". The answer is clearly "yes".
For \(n=2\) and \(n=3\), you should be able to convince yourself that it's impossible. It's harder to convince youself what's going on for larger value of \(n\), but I can tell you that
for \(n=4\) there are no solutions. Similarly for \(n=5\), \(n=6\) and \(n=7\) there are no solutions.
You may be starting to think that for any \(n\) except 1 there won't be solutions, but surprisingly there are 18656 solutions for \(n=8\) (or 2332 solutions if you count rotations and
reflections as the same solution). For \(n=9\) (the 2025 version of the puzzle), there are also a lot of solutions. I wrote some code for Matt to find them all: there are 1730280 of them (or 216285
if you count rotations and reflections as the same solution). You can download a zip file containing all the solutions from Zenodo.
Let me know if you do anything interesting with these solutions.
![](javascript:showlimage("partridge-solution.png"))
One of the solutions for \(n=9\)
None of the solutions for \(n=8\) or \(n=9\) has rotational or reflectional symmetry. I conjecture that there are no symmetric solutions for any \(n\) greater than this: it's reasonably easy to explain why there can never be a solution with rotational symmetry (unless \(n=1\)), but I haven't yet found a good justification for why there
aren't reflectionally symmetric solutions.
For \(n=10\), it is currently unknown how many solutions there are and so the OEIS sequence
(that gives the counts if rotations and reflections count as the same solution) stops at \(n=9\). My code that generated all the solution for \(n=9\) took around a week to find
all the solutions, so very much isn't capable of working out the number of solutions for \(n=10\).
Heat maps
Once I had the list of all solutions, I decided to make some heat maps to show where each piece
was most commonly placed. Here's the heat map for the 1×1 square:
![](javascript:showlimage("partridge-1-heatmap.png"))
Heat map of the location of the 1×1 square in the puzzle for \(n=9\): white squares will never contain the 1×1 square; the darker the red, the more likely the position is to contain the 1×1 square.
The amount of white (or near-white) in the plot surprised me: there's some positions that the 1×1 squares is placed in a lot and it nearly never ends up in many places. Here's the heat maps for the 2×2 to 9×9 squares:
![](javascript:showlimage("partridge-2-heatmap.png"))
![](javascript:showlimage("partridge-3-heatmap.png"))
![](javascript:showlimage("partridge-4-heatmap.png"))
![](javascript:showlimage("partridge-5-heatmap.png"))
![](javascript:showlimage("partridge-6-heatmap.png"))
![](javascript:showlimage("partridge-7-heatmap.png"))
![](javascript:showlimage("partridge-8-heatmap.png"))
![](javascript:showlimage("partridge-9-heatmap.png"))
Heat maps of the locations of the 2×2 to 9×9 squares for \(n=9\)
×4 ×2 (Click on one of these icons to react to this blog post)
You might also enjoy...
Comments
Comments in green were written by me. Comments in blue were not written by me.
Hi,
I am the author of the OEIS sequence. It's a pity that the sequence was not mentioned in Matt Parker's video.
Earlier this year I've made some analysis of the solutions: https://habr.com/ru/articles/889958/
In particular, there are solutions where all squares from 1 to 9 stack in one row or column (1+2+...+9 = 45).
As for the symmetry, the proof is the following: The symmetry could be horizontal (which is nearly the same as vertical) or diagonal.
In case of horizontal, the square of size 1 must be located on the center line. It will be either near the wall, or between 2 larger squares, that are centered on the center line. In both cases a lane of width 1 arises, that cannot be filled with any other square.
In case of diagonal, the square of size 1 must be on the diagonal and at first sight there is no lane of width 1. But, as long as you put all diagonal squares and then any square adjacent to the square of size 1, such a lane arises.
Your heatmap for size 1 is great!
×1 ×1
I am the author of the OEIS sequence. It's a pity that the sequence was not mentioned in Matt Parker's video.
Earlier this year I've made some analysis of the solutions: https://habr.com/ru/articles/889958/
In particular, there are solutions where all squares from 1 to 9 stack in one row or column (1+2+...+9 = 45).
As for the symmetry, the proof is the following: The symmetry could be horizontal (which is nearly the same as vertical) or diagonal.
In case of horizontal, the square of size 1 must be located on the center line. It will be either near the wall, or between 2 larger squares, that are centered on the center line. In both cases a lane of width 1 arises, that cannot be filled with any other square.
In case of diagonal, the square of size 1 must be on the diagonal and at first sight there is no lane of width 1. But, as long as you put all diagonal squares and then any square adjacent to the square of size 1, such a lane arises.
Your heatmap for size 1 is great!
Danila P.
×1 ×1 @Oleg:
The includes got filtered:
Util.h
//#include [bits/stdc++.h] // not including all
#include [filesystem] // just include what's needed
#include [array] // just include what's needed
#include [mutex] // just include what's needed
:)
The includes got filtered:
Util.h
//#include [bits/stdc++.h] // not including all
#include [filesystem] // just include what's needed
#include [array] // just include what's needed
#include [mutex] // just include what's needed
:)
Lord Sméagol
@Oleg:
I removed my macros:
#define __tzcnt_u32(v) ((v) ? (_tzcnt_u32(v)) : (32))
#define __lzcnt32(v) ((v) ? (_lzcnt_u32(v)) : (32))
replacing them with simple inline code
Util.h
//#include // not including all
#include // just include what's needed
#include // just include what's needed
#include // just include what's needed
#if 1 // use safe localtime
struct tm buf; // use safe localtime
auto err = localtime_s(&buf, &cur_time); // use safe localtime
return std::put_time(&buf, "%F %T"); // use safe localtime
#else // use safe localtime
return std::put_time(std::localtime(&cur_time), "%F %T");
#endif // use safe localtime
State.h
changed _mm_set_epi8(0x80 to -0x80 to stop warnings
inline replacement:
//int i = __tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
int i = _tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
inline replacement:
//int last_idx_before_mid = 31 - __lzcnt32(off_mask); // for no BMI; without zero test, as not needed here
int last_idx_before_mid = _lzcnt_u32(off_mask); // for no BMI; without zero test, as not needed here
Solver.h
inline replacement:
//return ini.size(); // to stop warning
return (int)ini.size(); // to stop warning
inline replacement:
//const int dim = __tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
const int dim = _tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
I tried '9' runs: with asserts: 10:31, without: 10:18 (saved 2%)
A minute slower than the faulty version, but still not too bad for a 2013 (Q3) CPU :)
I removed my macros:
#define __tzcnt_u32(v) ((v) ? (_tzcnt_u32(v)) : (32))
#define __lzcnt32(v) ((v) ? (_lzcnt_u32(v)) : (32))
replacing them with simple inline code
Util.h
//#include // not including all
#include // just include what's needed
#include // just include what's needed
#include // just include what's needed
#if 1 // use safe localtime
struct tm buf; // use safe localtime
auto err = localtime_s(&buf, &cur_time); // use safe localtime
return std::put_time(&buf, "%F %T"); // use safe localtime
#else // use safe localtime
return std::put_time(std::localtime(&cur_time), "%F %T");
#endif // use safe localtime
State.h
changed _mm_set_epi8(0x80 to -0x80 to stop warnings
inline replacement:
//int i = __tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
int i = _tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
inline replacement:
//int last_idx_before_mid = 31 - __lzcnt32(off_mask); // for no BMI; without zero test, as not needed here
int last_idx_before_mid = _lzcnt_u32(off_mask); // for no BMI; without zero test, as not needed here
Solver.h
inline replacement:
//return ini.size(); // to stop warning
return (int)ini.size(); // to stop warning
inline replacement:
//const int dim = __tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
const int dim = _tzcnt_u32(mask); // for no BMI; without zero test, as not needed here
I tried '9' runs: with asserts: 10:31, without: 10:18 (saved 2%)
A minute slower than the faulty version, but still not too bad for a 2013 (Q3) CPU :)
Lord Sméagol
@Oleg: Happy new year!
I just added this:
#if 0
int last_idx_before_mid = 31 - __lzcnt32(off_mask); // 31 - LZCNT ==> index of MSb
#else
// if off_mask can never be zero, no need for check to override BSR result
assert(off_mask);
// a '9' run didn't reveal any 0 [you would know for sure for other sizes]
// need unsigned long result
unsigned long last_idx_before_mid;
// get index of MSb [no need for adjustment if off_mask can never be zero]
_BitScanReverse(&last_idx_before_mid, off_mask);
#endif
a run of '9' now produces the correct result: 1,730,280 :)
I just added this:
#if 0
int last_idx_before_mid = 31 - __lzcnt32(off_mask); // 31 - LZCNT ==> index of MSb
#else
// if off_mask can never be zero, no need for check to override BSR result
assert(off_mask);
// a '9' run didn't reveal any 0 [you would know for sure for other sizes]
// need unsigned long result
unsigned long last_idx_before_mid;
// get index of MSb [no need for adjustment if off_mask can never be zero]
_BitScanReverse(&last_idx_before_mid, off_mask);
#endif
a run of '9' now produces the correct result: 1,730,280 :)
Lord Sméagol
@Lord Sméagol: Hello and happy New Year!
9 minutes is cool!
The answer is wrong because of _lzcnt instruction, as you suspected, as turns out it works differently on different cpus: https://nextmovesoftware.com/blog/2017...
With this error, solutions having 1x1 square directly in the center are not counted.
I guess, gcc/clang do it correctly because I specify -march=native (so it checks cpu and generates correct instruction), and run where I compile. But it's a potential problem I probably need to add some assertions to the code.
Maybe on your hardware you can either use WSL and clang compiler, or set constexpr bool USE_SSE_QUADRANT_FILL=false, to fall back to slower.
You could also try to use BitScanReverse instead of __lzcnt, but it has different input/output so I'm not sure how hard would that be to fix it.
9 minutes is cool!
The answer is wrong because of _lzcnt instruction, as you suspected, as turns out it works differently on different cpus: https://nextmovesoftware.com/blog/2017...
With this error, solutions having 1x1 square directly in the center are not counted.
I guess, gcc/clang do it correctly because I specify -march=native (so it checks cpu and generates correct instruction), and run where I compile. But it's a potential problem I probably need to add some assertions to the code.
Maybe on your hardware you can either use WSL and clang compiler, or set constexpr bool USE_SSE_QUADRANT_FILL=false, to fall back to slower.
You could also try to use BitScanReverse instead of __lzcnt, but it has different input/output so I'm not sure how hard would that be to fix it.
Oleg
@Oleg: I pulled your code into Visual Studio 2026 and dealt with some warnings:
The COLLAPSES initializer was easy: Use (char) for 0x80
I changed unsafe localtime to:
struct tm buf;
auto err = localtime_s(&buf, &cur_time);
return std::put_time(&buf, "%F %T");
I did a quick change of __tzcnt_u32, __lzcnt32 to use _tzcnt_u32, _lzcnt_u32
Setting the compiler to use AVX and optimize for speed.
An '8' run worked, so I tried '9'
And it found only 1,729,930 solutions!
I suspected _tzcnt_u32, _lzcnt_u32 might be causing it, so I covered that:
#define __tzcnt_u32(v) ((v) ? (_tzcnt_u32(v)) : (32)) // Match BMI : should return 32 for value 0
#define __lzcnt32(v) ((v) ? (_lzcnt_u32(v)) : (32)) // Match BMI : should return 32 for value 0
but it didn't fix it.
Anyway, I decided to test multi-threading.
First I hunted for the initial depth sweet spot:
>Puzzle_Oleg.exe run 9 8 24
>Puzzle_Oleg.exe run 9 9 24
...
>Puzzle_Oleg.exe run 9 18 24
>Puzzle_Oleg.exe run 9 19 24
And found that 15 was fastest. [It didn't like 19]
'9' run [with the 1,729,930 problem] on Xeon E5-2697-v2
12t: 11m 52s
24t: 9m 1s
so HyperThreading is helping by about 48%
The COLLAPSES initializer was easy: Use (char) for 0x80
I changed unsafe localtime to:
struct tm buf;
auto err = localtime_s(&buf, &cur_time);
return std::put_time(&buf, "%F %T");
I did a quick change of __tzcnt_u32, __lzcnt32 to use _tzcnt_u32, _lzcnt_u32
Setting the compiler to use AVX and optimize for speed.
An '8' run worked, so I tried '9'
And it found only 1,729,930 solutions!
I suspected _tzcnt_u32, _lzcnt_u32 might be causing it, so I covered that:
#define __tzcnt_u32(v) ((v) ? (_tzcnt_u32(v)) : (32)) // Match BMI : should return 32 for value 0
#define __lzcnt32(v) ((v) ? (_lzcnt_u32(v)) : (32)) // Match BMI : should return 32 for value 0
but it didn't fix it.
Anyway, I decided to test multi-threading.
First I hunted for the initial depth sweet spot:
>Puzzle_Oleg.exe run 9 8 24
>Puzzle_Oleg.exe run 9 9 24
...
>Puzzle_Oleg.exe run 9 18 24
>Puzzle_Oleg.exe run 9 19 24
And found that 15 was fastest. [It didn't like 19]
'9' run [with the 1,729,930 problem] on Xeon E5-2697-v2
12t: 11m 52s
24t: 9m 1s
so HyperThreading is helping by about 48%
Lord Sméagol
Add a Comment
Archive
Show me a random blog post 2026
May 2026
World Cup stickers 2026Apr 2026
A new puzzle every dayMixing Wordle with other games
Feb 2026
Christmas (2025) is over 2025
Dec 2025
Christmas card 2025Nov 2025
Christmas (2025) is coming!Sep 2025
The partridge puzzleAug 2025
TMiP 2025 puzzle huntJun 2025
A nonogram alphabetMar 2025
How to write a crossnumberJan 2025
Christmas (2024) is overFriendly squares
2024
Dec 2024
A regular expression Christmas puzzleChristmas card 2024
Nov 2024
Christmas (2024) is coming!Feb 2024
Zines, pt. 2Jan 2024
Christmas (2023) is over 2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
Tags
numerical analysis raspberry pi palindromes crosswords hannah fry mathsjam numbers data visualisation big internet math-off speed ucl turtles chebyshev radio 4 zines wordle alphabets tmip polynomials graphs tennis signorini conditions mathslogicbot reuleaux polygons programming preconditioning javascript triangles game of life tetris pokémon coins craft rugby fence posts graph theory pi logo people maths recursion cambridge machine learning plastic ratio 24 hour maths live stream frobel electromagnetic field harriss spiral latex asteroids edinburgh crossnumbers bempp interpolation manchester london folding tube maps exponential growth python data captain scarlet realhats misleading statistics pokémon wordle errors advent calendar braiding hyperbolic surfaces coventry hexapawn propositional calculus wool christmas books reddit accuracy geogebra inverse matrices final fantasy gaussian elimination sport matt parker rust boundary element methods friendly squares flexagons noughts and crosses binary games european cup pi approximation day arrangement puzzles football datasaurus dozen stirling numbers php finite group fractals computational complexity finite element method mean guest posts folding paper kings ternary runge's phenomenon platonic solids golden ratio bubble bobble phd dragon curves error bars pac-man databet quadrilaterals nonograms geometry mathsteroids crossnumber fonts weak imposition probability national lottery weather station curvature pizza cutting kenilworth approximation sorting video games menace anscombe's quartet bluesky draughts martin gardner newcastle a gamut of games statistics oeis light warwick thirteen matrix of minors puzzles countdown nine men's morris cross stitch bodmas the aperiodical rhombicuboctahedron london underground royal baby game show probability news dinosaurs world cup royal institution correlation gerry anderson standard deviation stickers matrix multiplication crochet wave scattering logic pythagoras estimation arithmetic talking maths in public sound trigonometry dates pascal's triangle bots manchester science festival sobolev spaces logs golden spiral partridge puzzle hats map projections youtube matrix of cofactors go chess regular expressions chalkdust magazine christmas card gather town simultaneous equations determinants inline code squares convergence dataset matrices© Matthew Scroggs 2012–2026