Monday, November 02, 2020

sudoku? yunohu tugotu

Nia has been getting into some more adult puzzle-wrangling lately, including sudoku, which reminded me of a couple of things that intrigued me about it back when it was suddenly A Thing a few years ago (mid-2000s seems to have been the start of sudoku-mania in the Western world). Firstly, I'm still slightly vexed at how many people mispronounce it, but I have come to accept that some people just seem to have a general sort of word-blindness and once they've fucked something up once will never be able to (or, more judgmentally, care enough or be capable of exercising enough intellectual curiosity to) avoid continuing to fuck it up in perpetuity. I also experience slight annoyance every time someone describes them as "mathematical puzzles", generally as an excuse to avoid engaging with them, since they are clearly nothing of the sort. The usual set of nine things arranged in the grid is a set of numbers, admittedly, but it could just as easily be any other set of nine distinct things; there's no mathematics involved.

I dabbled with quite a bit of sudoku back in the day, and I might still have a go if I happen across one in a magazine during an idle moment, but the thing that always intrigued me about them, more than the actual solving of them, was how the partly empty grids were constructed. Clearly the starting point is a fully-filled in 9x9 grid containing the "solved" puzzle, and the challenge (essentially the reverse of the "actual" puzzle) is to remove a number of the values from the grid until you arrive at a grid (the starting grid for the solver) which is acceptably "hard" depending on what sort of a challenge you're aiming to provide, retains enough information for the solver to be able to reconstruct the grid you started with, and, moreover, for that grid to be the only valid one reconstructible from the set of starting values. 

This Wikipedia page has what appears to be a good and comprehensive summary of most of the relevant mathematics (unlike the puzzle-solving itself this undoubtedly is a mathematical puzzle); on the other hand it might be utter horseshit, I'm not really qualified to judge. The bit that is of interest to the layperson, though, is this section wherein it is revealed that the minimum number of clues you need to provide for a uniquely-solvable puzzle is 17, and that this number varies depending on the specific characteristics of the grid layout you've chosen.

Similar thoughts occurred to me during a game of The Genius Square, a game I was given for Christmas last year and which Nia has taken to with frightening speed, with Alys not far behind, as the picture below shows. 

Basically this is a sort of horizontal Tetris where you have to fit a set of 2-D pieces into a grid, the twist being that the grid is a slightly different shape every time owing to the presence of seven "blockers", whose placement is dictated by a set of dice.

The parallel to what you might call the sudoku meta-problem here is: given the set of pieces you're provided with, you can clearly construct a theoretical blocker placement which would make filling in the grid impossible (see below). 

So there must be some constraint which ensures that this can never happen, and the clue is in the claim made on the box that there are 62,208 distinct puzzle layouts. Now there are seven blockers and therefore seven dice and therefore in theory 67=279,936 possible permutations; a moment's thought should reveal that this is impossible, though, as there are 42 dice faces and only 36 squares, so some square addresses must appear in more than one place. And sure enough while 5 of the 7 dice have six distinct square addresses on them, the sixth has four (two appearing twice) and the seventh has just two (appearing three times each). Sure enough if you do the maths 6x6x6x6x6x4x2 turns out to be 62,208.

So what the three diagrams above show is as follows: the first one just shows what values appear on each face of the seven dice. The second shows, for each square in the grid, how many distinct dice faces it appears on (and therefore indicates how likely it is to come up during a random throw of all seven dice). The third, which is probably the most interesting (though clearly this is all relative), divides the grid up into seven "zones", each corresponding to the set of values contained on a single die. The important point here is that for each of the seven coloured zones, you will only ever have a single blocker in that zone during a game. Note also the rotational symmetry between, in particular, zones 2 and 5, and 3 and 6. You can see how the corners are the "awkward" spots and how it'd be desirable to increase the likelihood of having a blocker in a corner (and that the dice configuration ensures that you'll always have at least one corner blocked), but how you get from there to a mathematical demonstration that the dice layout provided guarantees a solution in every case I have no idea. 


everlands said...

Ah, the Happy Puzzle Company!

Can I just say, what an absolutely fantastic website they have! I'd like to shake the hand of whoever built that!


electrichalibut said...

One of yours? Nice.