Shimata!

Every morning I take (sic) The Herald.  Notice I don’t “get” my newspaper, I take it.  By the bye, I don’t take cream and sugar, I “have” cream and sugar (actually I don’t) and I don’t have a good breakfast, I “make” a good breakfast even if I don’t make it myself.  Then I sit with my coffee and read the Letters Page.  What with Brexit and Indyref 2, politics in Scotland at the moment is somewhat polarised, and in an effort to be impartial, The Herald tends to print letters from Camp A en masse on Monday, and then from Camp B on Tuesday.  Then Camp A ripostes on Wednesday, and so on.  People get exercised, and the tone can become sour, at which point, like Monsieur Manette in Dickens’ A Tale of Two Cities, coping with his post-traumatic stress disorder by returning to his cobbler’s last, I turn to the Puzzles Page.  The puzzles are either literary or numerical.  I usually do the literary ones and if I stray into the numerical I know my PTSD is particularly bad.  It’s a form of addiction really.

This morning’s letters are all about Brexit.  A new word has crept into the Brexit lexicon: Brexodus.  It describes the net fall in the UK immigration figures.  The odd thing about Brexodus is its pejorative connotation.  For years the government has been promising to get the immigration figures down to “the tens of thousands”, and for years the opposition has been lambasting it for failing to do so.  Control of immigration is one of the principal Brexit aspirations.  But now that the trend is swinging in that direction there seems to be general dismay rather than euphoria.  How can this be?  The answer lies in the word “control”.  The government wants to control who comes in and who leaves.  They want to cherry pick.  But the Eastern European cherry pickers have made their own minds up and are voting with their feet.  They will reap a harvest elsewhere.

As the negotiations in Brussels proceed, or stall, I predict we will need a whole thesaurus of neologisms.  We could use the Puzzles Page to generate them.  (You know you’re in a bad way when you start to make puzzles up.)  How many Br-words can you coin?  Less than 5 – brexcruciating; 5- 10 – brexiguous; 10 – 15 – brexcellent; more than 15 – brexcessive.

So…

Brexpletive deleted – minutes of the negotiation, redacted.

Brexocet – rebranding of Scud missile.

Brexcalibur – rebranding of Trident.

Brexcrement – exported nuclear waste.

Brex-Cathedra – intervention of Archbishop of Canterbury.

Brexaggeration – £350m weekly to NHS.

Brexorcist – anyone who can get us out of the mess we are in.

Brexterminate – latest Dalek trope or meme

Brexeunt – fall of the government.

You know you’re in a bad way when you start to make puzzles up.  I’ve recently found myself wondering how Sudoku puzzles are generated.  Sudoku is apparently a shortened version of the Japanese suji wa dokushin ni kagiru which means “the digits are limited to one occurrence”.  Even so there are, according to Professor Ian Stewart, 6,670,903,752,021,072,936,960 ways of filling out the typical 9 x 9 Sudoku grid.  I consulted his book Professor Stewart’s Incredible Numbers (Profile Books 2015) hoping to get some hints on how to solve the puzzles, and was somewhat discouraged, though not surprised by his statement, “the methods are too complicated to describe here, and can best be summarised as systematic trial and error.”  That fits in with my experience.  There are usually two Sudokus in the paper, one easy and one difficult.  I find that the easy one can usually be solved by an unbroken series of logical steps; you enter a number into a square confident that no other number will fit.  This added piece of information allows you to enter the next number with the same certainty, and so proceed until the grid is full.  The only potential snag is to make a mistake through carelessness.  You discover it further down the track and then the whole thing becomes difficult to unwind because you can’t identify when and where you made your mistake.  You mutter to yourself in a breathless Japanese whisper, “Shimata!”  Shimata, according to Ian Fleming in his magnificent You Only Live Twice means “I have made a mistake” or, as Mr Bond translates it more pithily, “Freddie Uncle Charlie Katie!”  Ah so desu ka!

The “hard” Sudoku does not seem to offer an unbroken line of reasoning and indeed you seem to need to fall back on Prof Stewart’s trial and error.  Best use pencil and rubber.  But what’s the point?  If the puzzle has a unique solution, there must be a rational way of reaching it.  Well, that’s an axiom.  I sat down with pencil and paper and tried to figure out the anatomy of Sudoku from first principles.

I know what you’re thinking.  Don’t go there.  It’s Mulholland Drive.

Just in case you don’t know the rules:  the Sudoku grid is a grand square of 81 squares, 9 x 9, rather like a chess board with an extra row and an extra column.  The grand square is subdivided into 9 subsets each of 3 x 3 squares.  The digits one to nine occur once, and only once (suji wa dokushin ni kagiru!) in every row, column, and subset, and our task is to fill the boxes with the right digits, the compiler having inserted for our benefit a handful of numbers to get us started.  This immediately begs the question: how does the compiler generate the puzzle, and know the puzzle has a unique solution?

It occurred to me to simplify the problem by reducing the size of the grid.  Instead of having a side of length 9, (3 squared), reduce it to 4 (2 squared) and use only the numbers 1, 2, 3, and 4.  This is now a grand square of 16 squares divided into four subsets each of 4 squares (2 x 2).  I know I’m straying into dangerous territory here.  My readership will have dwindled down to one mathematician (I know who you are) who will see I am making a Terrible Mistake.  What the hell.

Let us now consider the number of ways a 2 x 2 subset can be filled in.  This becomes an algebraic problem in “permutations and combinations” analogous to the following: four people go to the theatre.  They have seats in the back stalls – row X 1 and 2 and, immediately behind, row Y 1 and 2.  How many different ways can the theatre-goers arrange themselves?

Well, X1 can be filled in 4 different ways, and once it is filled, X2 can be filled in 3 different ways, and once it is filled, Y1 can be filled in 2 different ways, and once it is filled, Y2 can only be filled one way.  So there are 24 possible arrangements, that is, factorial 4 or 4!

Put this into the context of the 4 x 4 Sudoku square.  It has four subset quadrants and we now know that there are 4! – or 24 – ways of filling in a given quadrant, say the bottom left.  Once the minisquare is filled, move to the one on its right.  Now there are only two ways of inserting numbers in each row (or column) of the minisquare, so there are a total of 4 ways of filling in the second minisquare.

Now move to the minisquare on the top left of the puzzle.  The situation is exactly the same as with the previous minisquare.  There are four possible solutions.  Move finally to the last minisquare.  Each square, therefore the minisquare as a whole, has a unique solution.

Hence the number of possible solutions for a 4 x 4 sudoku puzzle is 24 x 4 x 4 x 1 or 384.

Clearly we now need to consider the actual 9 x 9 Sudoku puzzle or, better still, create a formula for any n x n puzzle using n digits.  The fact that Prof Stewart tells us the answer for the 9 x 9 grid is 6,670,903,752,021,072,936,960, is daunting.

Think I’ll try Kakuro.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s