Math Central - mathcentral.uregina.ca
Problem of the Month
 Currentproblem Recent problemswith solutions
 Older problems from 2005/2006 06/07 07/08 08/09 09/10 10/11 11/12

Solution for Summer 2008

The solution:

. . .The door opened and the seven brothers rushed out of the cellar, out of
the house, through the woods to a clearing where they ducked just as the house
blew up behind them. They had escaped just in time.
When at last they recovered their breath, they noticed that each of them
had kept the scrap of paper on which they had tried to solve the sudoku puzzle.
By then they realized that their younger brother must have known something
that they didn’t, and asked him how he solved the puzzle. This is what he said:
“Before the rat destroyed the bottom left corner, the puzzle must have looked
something like this:

Some of these question marks were blank cells, but others were numbers in
the original puzzle, which forced a unique solution to the problem (as told in the
letter). With these number removed, the puzzle did not become impossible; on
the contrary, we found out that many solutions are now possibles. My challenge
was to find the unique solution of original puzzle among the many possibilities
of the new grid. I had to avoid making guesses, and fill in a number in a cell
only when I knew for sure that it MUST go there because of one of the following
reasons:

• All the other numbers are known to appear elsewhere in the same row,
column or three by three square.

• This number cannot appear elsewhere in the same row, column or three
by three square.

With these rules, I could fill the grid partially, as follows:

All of your solutions agree with mine up to this point. But this was as far as
I could go without making guesses. Had the bottom left square been intact,
I may have been able to continue in this way, and not only find the unique
solution, but also PROVE that my solution were indeed the unique solution
of the original puzzle. With the bottom left corner destroyed, this option was
gone. So, I had to resort to an unconventional method. I used the uniqueness
of the original solution as an HYPOTHESIS, rather than trying to prove it:
Only the 3, 4, 5 are missing in the top right square, and only the 4 and 5 are
missing the bottom right square. The top 3 goes in column 7, either in row 1
or row 3. Could the 3 go in row 1? There is no apparent contradiction; indeed,
one of your solutions has the 3 in row 1. But in this case the fours and fives of
rows 3 and 8 appear in some order in columns 7 and 8, and we get a SECOND
solution by interchanging them. However we know that the original puzzle had
a unique solution. This means that the missing bottom left corner contained
information which at some point would have blocked the 3 from appearing in
row 1, column 7. Therefore there must be a 3 in row 3, column 7.
This in turn allowed me to fill the puzzle a little more, by putting in the 3
in the top left corner, then completing the top right and bottom right squares.
Afterwards the puzzle looked like this.

I then turned to the top left square, which could be completed by putting
in the 5 and the 6 in some order in the two empty cells. Again I found no
contradiction in putting the 5 in row 3, column 2, (indeed one of your solutions
has the 5 there), except that it would lead to a second solution obtained by
interchanging the 3 and the 5 in the top left and top right squares. So, I
concluded that the original bottom left square would at some point have ruled
out the 5 in this position, and put the 5 in row 3, column 1, and a 6 in row 3.
At this point I was able to fill in the puzzle a lot more:

Only the 4 and the 5 were missing in the bottom left corner. I noticed that
by putting the 4 in column 2 and the 5 in column 3, I got multiple solutions.
So, they had to go the other way around. At that point I had reconstituted the
original bottom left corner, and I could complete the original puzzle.”

So, this is how Hop o’ My Thumb saved his family one more time. The seven
brothers went back to see the remains of the house. Everything was destroyed
and there was nothing left to salvage, not a bonnet, not a breadcrumb and not
even a feather. So, they parted ways again and returned to their lives with their
newfound bit of wisdom, which is indeed worth more than treasures of gold and
diamonds.

Comments In “Sudoku squares and chromatic polynomials” [Notices of the
Amer. Math. Soc., 54 (2007) no. 6, 708-717], A. Herzberg and R. Murty link
Sudoku puzzles to graph colouring. Our summer problem was inspired by an
application of the “Kempe chain argument” to Sudoku puzzles. This argument
was introduced by Kempe in his 1879 attempt to prove the famous 4-colour
problem which states that four colours always suffice to colour the countries in
a map so that neighbouring countries get different colours. However, Kempe’s
argument was incomplete, and the four colour problem remained open until
complete proofs were given by Appel and Hacken in 1976 and by Robertson,
Sanders, Seymour and Thomas in 1996.

We received complete solutions to our problem from Philippe Fondanaiche
(France), Minghua Lin (China), Jerry Powidajko (Canada), Gérard Billion
(France), Jose Arraiz (Brazil), Jacques Mertzeisen (France), Patrick J. LoPresti
(USA), Zachary Friggstad (Canada), Matthew Lim (USA) and Bojan Basic (Serbia). Like the modern solvers of the four colour problem, most of our solvers used computers and showed that with the bottom left corner chewed out, the puzzle had 26 solutions. We provide a link below to Friggstad’s solution and program, to
Fondanaiche’s computer-free solutions and to Lim's computer-free solution and computational solution using Donald Knuth's "dancing links X" algorithm.

 Math Central is supported by the University of Regina and the Pacific Institute for the Mathematical Sciences.
 about math central :: site map :: links :: notre site français