The great search for the 16-clue Sudoku: computers, math, and the nature of proof

A 30-clue Sudoku puzzle. Image from WikimMedia Commons

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 possible completed Sudoku 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.


This entry was posted in Uncategorized. Bookmark the permalink.

124 Responses to The great search for the 16-clue Sudoku: computers, math, and the nature of proof

  1. Elexusbet says:

    Good text bro. thank you. Nice Article

  2. final ank says:

    this is one of the greatest ways to learn things about a company.
    harvard is one of the greatest universities of all time.

  3. matka 420 says:

    keep post good things

  4. satta matka says:

    We know from experience that drinking water inside building plumbing acts differently than when it is in the water distribution system (the water mains outside, under the streets). On this page, we try to explain a couple of the things that make building plumbing so complex .

  5. boss matka says:

    awsome blogs man

  6. Amazingly content and so useful sharing.

  7. Instagram hesap kurtarma işlemi bazı durumlarda son derece gerekli olabiliyor iken bazı durumlarda göz ardı edilebiliyor. Instagram hesapları genellikle bahis ve çeşitli illegal reklam yapan kişiler-çeteler tarafından hedef alınmaktadır. Organik takipçiye sahip hesaplar çeşitli yöntemlerle çalınır ve kişinin hesabından herkesin göreceği şekilde hikaye veya gönderi paylaşım yapılır. Diğer yandan, Instagram hesabınıza girememeniz hesabınızın çalındığı anlamına da gelmeyebilir. Instagram hesap kurtarma hakkında daha fazla bilgi edinin!

  8. emir eymen says:

    thanks for this information

  9. emir eymen says:

    thanks for this information

  10. emir eymen says:

    thanks for this information

  11. Uygun fiyata vpills Hap Satış Adresi


  12. Yavuz Alkın says:

    Uygun fiyata Viagra 100 Mg Hap Satış Adresi


  13. Uygun fiyata Cialis 100 Mg Hap Satış Adresi


  14. Uygun fiyata vega 100 Mg Hap Satış Adresi


  15. Emre Korkmaz says:

    Uygun Fiyata Cinsel Performans Ürünleri


  16. satta matka says:

    Awesome blog that features articles offering me the intended recipient you are not understand the perfeto 7

  17. final ank says:

    This is a indian matka number of learning and smart ways of learning and excelling

  18. meteor led says:

    I don’t know whether it’s just me or if perhaps everyone else encountering issues with your site. It appears as though some of the written text within your content are running off the screen. Can someone else please comment and let me know if this is happening to them too? This might be a issue with my internetbrowser because I’ve had this happen previously. Appreciate it

  19. fianl ank says:

    This is a indian matka number website

  20. It was useful content. Thanks

  21. Enkolaymatbaa ekibi olarak Kupa Bardak Baskı Hizmetleri vermekteyiz. En Uygun Kupa Bardak Baskı Fiyatları İçin Bizimle İletişime Geçin.


  22. I found your content worth reading. I would be very happy if you support me by reading my existing content on a blog.

    My blog address is https://terzimankeni.web.app/

  23. Vega 100 hap says:

    Vega 100 mg 4 lü tablet eczane güvenceli orijinal geciktirici ve sertleştirici ilaç kampanyalı satış sitesi Vega 100 fiyat

  24. Online eczane satış sitemizden kadınlar ve erkekler için en etkili cinsel sağlık ürünleri hakkında bilgi sahibi olabilir sipariş verebilirsiniz. Thanks for sharing. Cinsel İlaçlar

  25. Rulman says:

    Rulman, Keçe, Bilya, Redüktör, Sigma Profil, Segman, Kayış, CNC Rulmanları, Tane Bilya gibi bir çok çeşit ile 1959 yılından beri müşterilerimizin hizmetindeyiz.

  26. Thank you for this nice sharing.

  27. yasar öcal says:

    Selamlar, böyle yararlı makaleler yazarak sektöre katkı sağladığınız için teşekkür ederim. Bizler de Çağlayan Klima olarak Antalya’da klima montajı, klima bakımı, klima temizleme, klima takma, klima arıza, hizmetleri vermekteyiz. Saygılar sunarım. https://www.antalyaklimaservisleri.net/

  28. Ayeses Group says:

    Yangın Sonrası Temizlik
    Yangın sonrası temizlik konusunda ihtiyacınız olduğu her alanda etkili sonuçlar için hizmet alabilir ve bu şekilde daha kısa süre içinde yaşam alanlarını eskisi gibi kullanmaya devam edebilirsiniz. Oluşan yangının boyutlarına göre farklı şekillerde yapılacak olan işlemler ile alanda daha temiz bir alan oluşturulması sağlanır.

    Yangın sonrası temizlik konusunda ihtiyacınız olduğu her alanda etkili sonuçlar için hizmet alabilir ve bu şekilde daha kısa süre içinde yaşam alanlarını eskisi gibi kullanmaya devam edebilirsiniz. Oluşan yangının boyutlarına göre farklı şekillerde yapılacak olan işlemler ile alanda daha temiz bir alan oluşturulması sağlanır. https://www.ayesesgroup.com/hizmetlerimiz/istanbul-afet-sonrasi-temizlik/

  29. Re-Satr Evden Eve Nakliyat


    Re-Satr Nakliyat evden eve nakliye ve Taşımacılık sektöründe uzun yılların verdiği Hizmet sayesinde bir çok alanda gösterdiği başarı ile Türkiye’nin en ucra köylerine bile taşımacılık hizmeti vermekte dir nakilye firmaları arasında öncü olan firmamız sayesinde evinizde özenle alınıp paketlenen eşyalarınız asansörlü hizmetimiz ile istediğiniz adrese ayın özenle götürülüp teslim edilmektedir.

  30. İstanbul Güvenlik Kamera Hizmeti


    Teknoguvenlik34 sayesinde evinizde, villanızda, okullarda, Otoparklar, Kamu Kurum ve Kuruluşları, Ofisler, Avm veya iş yerinizin güvenliğini kolayca artırın. 2 megapiksel kameralı,5 megapiksel kameralı çeşitlerimiz mevcuttur. Full donanımlı sistemi sizlere sunmaktayız. Gündüz renkli kayıt yapar ve otomatik olarak gece görüşü moduna geçer. Güvenlik kamera sistemi ile ilgili detaylı bilgi için bizi arayabilirsiniz.

  31. good information. thanks a lot. good job.

  32. very good information. thanks. good luck..

  33. Thanks to these practices, which bring certain quality standards to companies by ISO (International Standards Organization), you can get all the necessary information to provide world-class service in production, export, R&D. In this direction, Prodan Quality Consultancy firm will lead you with its well-equipped team.

  34. ISO 9001: 2015 Quality Management System Certificate
    ISO 14001: 2015 Environmental Management System Certificate
    ISO 22000: 2018 Food Safety Management System Certificate
    ISO 27001: 2013 Information Security Management System Certificate
    ISO 45001: 2018 Occupational Health and Safety Management System Certificate
    Training and Consultancy Services

  35. Güzel bir çalışma

  36. Nice post! Thanks! This is significant information for me.

  37. Nice post! This is important information for me. Thanks!

  38. Takipçi satın al, instagram ucuz ve güvenilir takipçi ile instagram güvenilir ucuz takipçi satın al. En ucuz ve en güvenilir instagram takipçi sitesi; https://takipcisepette.com ile ucuz instagram takipçi satın al!

  39. Adl belge says:

    Friends, I think once the comment was about “The great search for the 16-clue Sudoku: computers, math, and the nature of proof”.

  40. Hmm.. It’s work for me.
    Just an information, if you need information about Pengertian Valve visit our website

  41. sohbet says:

    cafe sohbet mekani canli sohbet

  42. mehmet says:

    Türkiye’nin en hızlı ve evinden çıkmadan en çok para kazandıran sitesi ! Hemen üye ol sende kazanmaya başla !

  43. sattamatka says:

    love from bjp india

  44. turkchat says:

    teşekurler admin saol

  45. Thanks you very nice hand good.

  46. Aycup ® markamız ile önceliğimiz kurumsal firmaların ihtiyacı olan kullan- at ürünleri, karton bardak, kağıt bardak, tahta karıştırıcı ve ofis sarf malzemeleri tedariğini yapmaktayız.

    2012 yılında kendi müşteri portföyüne kısa bir zamanda sahip olan Aycup ® yaptığı yatırımlarla markasını karton bardak piyasasına kabul ettirmiş, karton bardak denilince akla gelen lider markası olmuştur.

    Kalitesi ile her geçen gün dikkat çeken karton bardak firması Aycup ® karton bardak, kağıt bardak, tahta karıştırıcı, plastik karıştırıcı ürünlerini cazip fiyatlar ile satışını yapmakta, halen sektörün lokomotifi halindedir. https://www.aycup.com.tr/iletisim

  47. Elektrikli scooter alanında hizmet veren ve birçok mikro mobilite aracının satışını yapan kaliteli bir alışveriş sitesidir. Escooter, elektrikli bisiklet, tek teker, hoverboard başta olmak üzere birçok mobilite aracını bulabilir, inceleyebilir ve güvenle sipariş verebilirsiniz. Yapmanız gereken tek şey internet sitesini ziyaret etmek ve beğendiğiniz ürünü sepete atarak satın almak. Siparişiniz güvenli bir şekilde kapınıza gelecektir.

  48. Seodemy says:

    Seo İle İlgili herşey

  49. teknodate says:

    Güncel Teknoloji Haberleri

  50. chat hup says:

    Thank you so much for this good share. you can

  51. lamhar says:

    Nice and good information.

  52. Oyun says:

    Oyun haberleri, Oyun incelemeleri ve daha fazlası.
    Epic Games, Metro: 2033 Redux’ı Ücretsiz Yaptı

  53. En son teknoloji haberleri, donanım haberleri burada. Akıllı telefon, tablet, donanım, yazılım haberleri, dünya ile aynı anda özgün olarak Tekno Bilim adamı websitesi

  54. hartono liem says:

    Nice and good information about sudoku.

  55. lab komputer says:

    amazing helpfully blog for everyone…

  56. Sofyan says:

    Thanks…Very interesting.

  57. Pingback: How Financial Leadership Development Can Improve Your Accomplishment - Evans shop

  58. Pingback: Eye Health Training – vmasksnapgcc

  59. Pingback: What is Your Law-school Definition of Regulation? - Brand Promotions

  60. Pingback: Biology or equal – how I realized! – Prism

  61. Pingback: Biology or similar – the way i acquired! – Chegou o Gás

  62. Pingback: What’s Science? | MBthin

  63. Pingback: The Importance of Having a Rally – Spark News NG

  64. Pingback: Massages: retraining to be a masseur / masseuse for. – Glactro

  65. Pingback: Maintenance little one resolve researching taxation. | MINERA P'HUYU YURAQ II EIRL

  66. Pingback: Oingo Boingo also takes tunes seriously. : Apex Youth Foundation Inc.

  67. Pingback: Getting the Optimal/optimally Computer Science Undergraduate Diploma - Eco House

  68. Pingback: Institute of Mathematics and computer scientific discipline. | Ornatos Embalagens

  69. Pingback: Drive note – an illustration. – Funnel Factor X Agency

  70. Pingback: translate high school degree or diploma. | House Cleaning and Maid Service in Phoenix, AZ | Maid Easy

  71. Pingback: Two Research: How will you secure a desired location themself. – Al-Ghani Solutions

  72. Pingback: translate high school degree or diploma. – Lê Hoàn Studio

  73. Pingback: App dual research projects: How do you apply perfect? - SoftwareVilla News

  74. Pingback: Cyber strike about the Institution of Giessen: What helps prevent the UW? – Vay ngân hàng

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

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

  77. Pingback: Notice Cooperative Learning Market « Hannaford Career Center

  78. 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

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

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

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

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

  83. Cool on with the kjd

  84. Dendy RO says:

    Hmm.. It’s work for me.
    Just an information, if you need information about Spesifikasi HP Xiaomi visit our website.

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

  86. 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

  87. Pingback: Emphasis Aspects of Power And Environmental Science - sparksinside

  88. Pingback: The Arithmetic learning foundation. – ImagineSecurity

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

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

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

  92. Pingback: Greatest Colleges For Compsci – CEMPIABI

  93. Pingback: Mathematics and Genealogy: A Match | Creative Wonder

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

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

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

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

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

  99. Pingback: Educator (m / w / d)

  100. Pingback: Advice On Glencoe Science – Digisoft

  101. Amber says:

    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.

  102. Hunter says:

    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? 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *