Sudoku (rules can be found here) has always had a problematic association with mathematics. A first reaction by the ‘man-on-the-street’ to all those numbers is that it’s “too math-y” — ironic, since the numbers are just employed as placeholders and could easily be replaced by letters, pictures, or other symbols. A Sudoku fan would counter with the (equally ironic?) retort “it’s not math at all — it’s just logic.” In any case, the pattern-searching and deductive reasoning employed in teasing out the unique solution are skills any mathematicians would find familiar.

However, the real math behind Sudoku starts to rear its head when we turn the problem around, and try to build Sudoku puzzles. We have to fill in enough boxes so that there is only one correct solution, but few enough that determining that solution presents a challenge. Generally speaking, the more clues we fill in the easier the puzzle becomes to complete.

Project idea:Work with a student (perhaps a motivated student studying probability or discrete math — anywhere that you are discussing combinations and permutations) to describe all possiblecompletedSudoku puzzles. Even this may be quite hard, in the end, but the process would be illuminating — just finding different ways of describing the problem would be a good challenge. How many ways of filling in nine digits in a 9×9 grid? How do we begin to eliminate “repetitions” in rows, columns, and regions? Etcetera.

An obvious question presents itself – what’s the “hardest” puzzle we can make? How few of the boxes can be filled in, and still give a unique solution? Examples have been found with as few as 17 clues. On the other hand, it is not hard to see that very few clues will not work — if we try to build a puzzle with only 7 clues, the solution cannot be unique (since we have only used 7 of nine digits, any solution we obtain can be transformed into a different solution by swapping all occurrences of the remaining two digits). But the gap between 7 clues and 17 is quite large — yes, it has been reduced further, but not by as much as you might expect (until this year, see below).

It is interesting to reflect on the status of this work in the relatively recent past — this post by Gordon Rolye on his blog SymOmega is about 15 months old, and asks (but doesn’t answer) the question “Is there a 16-clue Sudoku puzzle?” In one of the top comments, he provides a reasonable argument why he expects the answer is no:

Well, it is still open, but my hunch is that there is NO 16-clue Sudoku puzzle. A single 16-clue Sudoku puzzle would give us a whole bunch of 17-clue puzzles and given how hard it now seems to eke out a single extra 17-clue puzzle, I would guess that it just doesn’t happen.

**Computer-aided proof, and No 16-Clue Sudoku**

On New Year’s Day 2012, a team of researchers posted this article on the arXiv: There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem. Their proof is an interesting combination of subtle mathematics and brute-force computing. One might ask why we can’t just check all the possible 16-clue puzzles, and here we run into trouble with exponential growth — there are simply too many (waaaaaay beyond the combined computing power of every processor ever built by man). The mathematical subtlety arises in reducing the number of possible 16-clue puzzles to check (this is not, strictly speaking, the method, but it captures the essence). Even so, the number of possibilities is enormous, requiring about 7 million CPU hours to check them all. In the end, no such puzzle was found having a unique solution. Conclusion? The minimum number of clues required for a Sudoku puzzle must be 17. Here’s a nice video on the subject from the numberphile blog.

This amazing, and unsatisfying.

Amazing, because we have leveraged our hands-dirty, real-world, physics-harnessing technological abilities to extend our purely mathematical knowledge (where usually the information flows the other way, with mathematics offering assistance to the more-applied disciplines).

Unsatisfying for at least two reasons:

First, how do we know it’s right? No human has actually checked all the possibilities (nor will they!). Here, we rely on the correctness of the hardware and software that ran the computation — and, given our daily difficulties with computers, this is a leap of faith on a pretty high level. However, this is a tractable problem. For example, it is *much* easier to check the algorithm used than to check every aspect of the hardware and software that implements it — and if the algorithm is sound, and produces consistent results regardless of implementation, we can have some confidence that it really does what we want it to do.

Second, and more troubling from a mathematical perspective, is that this proof doesn’t offer any kind of *insight* into the problem. As mathematicians, we have a motivation to ask “why?” and we take great satisfaction when we finish a proof and finally understand not just the result but the *reason behind it*. Indeed, when a mathematician shares a proof with a colleague, the essence of what they are trying to communicate is *why* the result holds. So we ask:* Why* is 17 the minimum number of clues? How can we generalize this to higher-order puzzles? What’s the logical reason that no 16-clue puzzle will have a unique solution? The result is true, but the reason is still beyond us.

Pingback: Dental helper – schooling necessities, earnings. – JoVaSaMc

Pingback: Understanding The Chemistry Of Combination Science - Estucos y Morteros DECAL

Nice one

Pingback: Notice Cooperative Learning Market « Hannaford Career Center

Pingback: Until such time as further discover, only consider, and multimedia along with the sign up of brand new individuals can be done during the DHBW Stuttgart local library. – Hacked By Hunter Bajwa

Pingback: Why Would You Really Need The Science Of Your Head? – BHA CONCEPTION

Pingback: Access Science - Your Security Alternative For Faculties - dndigital

Pingback: Could Science and Religion Come Together? - iCare Compassion Ministries Foundation, Inc.

Pingback: Not for the faint of cardiovascular system – the twin analysis the tax place of work. – MinhoMática

Cool on with the kjd

I love this

Hmm.. It’s work for me.

Just an information, if you need information about Spesifikasi HP Xiaomi visit our website.

Pingback: Simply As You Will Find Many Types Of Muesumthat You Can Find Houston Museum Of Pure Science Solutions

Pingback: Financial hosts and hostesses monetary option as administrators / officials or employees for tax bill and fiscal regulators while using supervision of fees such as profitscorporation and tax, area shift and inheritance taxes. – Farmasi Üye Kayıt

Pingback: Emphasis Aspects of Power And Environmental Science - sparksinside

Pingback: The Arithmetic learning foundation. – ImagineSecurity

Pingback: User Product reviews: Just how can we finance our scientific tests. – RapidSofts

Pingback: Demo K-Order | Vocation like a specialist number in Bremen: Functional and filled with potential customers.

Pingback: Hardware and software options on the corporate and business circumstance design, conceive and develop. – Andrew Rwela

Pingback: Greatest Colleges For Compsci – CEMPIABI

Pingback: Mathematics and Genealogy: A Match | Creative Wonder

Pingback: Our March for Science amounts have increased with over 200% since this past year. | Ganymede International

Pingback: An Overview of This Differing Traits among Poetry and Arithmetic – Principal

Pingback: Mathematics Suggestions — Know More About Your Skills — Меджурнал

Pingback: Arithmetic Tricks - Know About Your Partner - hacked by ibna noman

Pingback: Uni, Academy, FH and TU – In which ought i investigation? – Hacked by Fighter Anas

Pingback: Educator (m / w / d)

Pingback: Advice On Glencoe Science – Digisoft

For those of you willing to try some minimal sudokus, I found this site that generates a lot of different ones: http://sudokus.co.nf/

All of the sudokus there only have 17 clues.

Very interesting. This reminds me of the quest for “God’s number” ie the minimum number of moves to solve any Rubik’s cube. An article by Rik van Grol gives a good summary.

It is strange to compare computer-aided-proofs, which are so brutally concrete, to set theoretic arguments that show an absolute statement is consistent with ZFC. They both provide essentially zero insight, but are located at completely opposite ends of the abstractness spectrum.

Maybe only very beautiful problems have “why” answers? Could you argue that since there are only a small number of “short explanations” it follows that most problems must be uninteresting, for purely combinatorial reasons? 🙂