[Turkmath:8141] Re: Ynt: sudoku

[Orcun Yaman]

Sayin Ulkudas,
Ciddi misiniz? yoksa ben bu isi beceremiyorum, onun icin mundar'dir mantigindan mi hareket ediyorsunuz?

Bugun bircok matematikcimiz ne ise yarayacagini muhtemelen kendilerinin de bilmedigi sorulari cozmek ile ugrasacagina, sudoku hakkinda calisma yapsalar, inanir misiniz Turkiye'nin bilgisayar bilimlerine/egitime katkisi artar.

Kalin saglicakla.

Orcun.


________________________________
 From: "meulkudas at mynet.com" <meulkudas at mynet.com>
To: muhammed.uludag at gmail.com 
Cc: turkmath at listweb.bilkent.edu.tr 
Sent: Sunday, January 22, 2012 3:26 PM
Subject: [Turkmath:8139] Ynt:  sudoku
 

sudoku = zaman israfı
kütleleri uyuşturmak için icat edilmiş yeni bir afyon/ibadet tarzı.
matematikçiye yakışan matematik yapmaktır.



>----- Özgün İleti -----
>Kimden : muhammed.uludag at gmail.com
>Kime : "turkmath at listweb.bilkent.edu.tr" <turkmath at listweb.bilkent.edu.tr>, gsu_math <gsu_math at yahoogroups.com>
>Gönderme tarihi : 08 Ocak 2012 Pazar 20:39
>Konu : [Turkmath:8119] sudoku
>
>Ref: arxiv.org/abs/1201.0749: There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem

Mathematicians Solve Minimum Sudoku Problem
Sudoku fanatics have long claimed that the smallest number of starting clues a puzzle can contain is 17. Now a year-long calculation proves there are no 16-clue puzzles

KFC 01/06/2012

10 COMMENTS

Sudoku is a number puzzle consisting of a 9 x 9 grid in which some cells contain clues in the form of digits from 1 to 9. The solver's jobs is to fill in the remaining cells so that each row, column and 3×3 box in the grid contains all nine digits.

There's another unwritten rule: the puzzle must have only one solution. So grids cannot contain just a few starting clues.

It's easy to see why. A grid with 7 clues cannot have a unique answer because the two missing digits can always be interchanged in any solution. A similar argument explains why grids with fewer clues must also have multiple solutions.

But it's not so easy to see why a grid with 8 clues cannot have a unique solution, or indeed one with 9 or more clues.

That raises an interesting question for mathematicians: what is the minimum number of Sudoku clues that produces a unique answer?

This is a question that has hung heavy over the Sudoku community, not least because they think they know the answer. Sudoku fanatics have found numerous examples of grids with 17 clues that have a unique solution but they have never found one with 16 clues.

That suggests the minimum number is 17 but nobody has been able to prove that there isn't a 16-clue solution lurking somewhere in puzzle space.

Enter Gary McGuire and pals at University College Dublin. These guys have solved the problem using the tried and trusted mathematical technique of sheer brute force.

In essence these guys have examined every potential 16-clue solution for every possible Sudoku grid. "Our search turned up no proper 16-clue puzzles, but had one existed, then we would have found it," they say.

That's an impressive feat. There are exactly 6, 670, 903, 752, 021, 072, 936, 960 possible solutions to Sudoku (about 10^21) . That's far more than can be checked in a reasonable period of time.

But as luck would have it, it's not necessary to check them all. Various symmetry arguments prove that many of these grids are equivalent. This reduces the number that need to be checked to a mere 5, 472, 730, 538.

So McGuire and co wrote a program called Checker to check each one of these grids for a 16-clue solution.

But the process of checking a single grid is itself tricky. One way to do it is to examine every possible subset of 16 clues to see if any of them lead to a unique solution. The trouble is that there are some 10^16 subsets for each grid.

Once again, a little mathematics come in handy. McGuire and co used some clever reasoning to show that certain subsets are equivalent to many others and this dramatically reduces the number of subsets that need to be checked.

Nevertheless, the resulting calculation is still a monster. The Dublin team say it took 7.1 million core-hours of processing time on a machine with 640 Intel Xeon hex-core processors. They started in January 2011 and finished in December.

The whole exercise may sound like a bit of mathematical fun but this kind of problem solving has many important applications. McGuire and co say the problem of Sudoku grid checking is formally equivalent to problems in gene expression analysis and in computer network and software testing.

So the Dublin team's methods for speeding up the calculation will have a direct impact in these areas too.

But while the result is clearly impressive, the Minimum Sudoku Problem isn't entirely laid to rest.

This problem is crying out for an elegant proof that allows us to "see" why the minimum number must be 17; rather like the proof that there can be no unique solutions for 7 or fewer clues.

A big ask, I know, but surely one worth aiming for.



Correction: this post was edited on the 6 January to reflect the argument that if an n-clue grid is uniquely solvable then adding a digit to make an n+1-clue grid must also be uniquely solvable. So if there are no uniquely solvable 16-clue grids, there cannot be any grids with fewer clues that are uniquely solvable. Thanks to RealMurph and abooij.

-- 
--
A. M. Uludag
http://math.gsu.edu.tr/uludag/


________________________________

_______________________________________________
Turkmath mailing list
Turkmath at listweb.bilkent.edu.tr
http://yunus.listweb.bilkent.edu.tr/cgi-bin/mailman/listinfo/turkmath
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://yunus.listweb.bilkent.edu.tr/cgi-bin/mailman/private/turkmath/attachments/20120122/eb899dd7/attachment.htm>