[Turkmath:8147] Re: Ynt: Re: Ynt: sudoku

24 Oca 2012 Sal 09:46:05 EET

Sayin Hocam,
Mutevazılik gosterip bagisladiginiz icin tesekkur ederim. Sizi tanimiyorum, emekli oldugunuza gore size gore hayli toy sayilirim. Yeniden ozur dilerim.
Yaptigim Turkce yanlisi icin de tekrardan kusuruma bakmayiniz. 'mundar' kelimesinin aslinin 'murdar' oldugunu pekala biliyorum, fakat bizim oralarda yoresel agizda 'mundar' seklinde kullanildigi icin o sekilde yazdim. Hani bir nevi espri olsun kabilinden, boyle yazacaginizi bilseydim dogrusunu yazardim. Su bir iki noktayi da belirtmeden gecemiyecegim.

Uslup konusu icerik icin birsey soyleyemenler icin siginilan uygun bir limandir. Bu gruba uzun zamandan beri uyeyim, benden cok buyuk hocalarimin birbirlerine yazdigi oyle mailler okudum ki; bir an icin ulkemizin unlu matematikcileri boyle mi dusunuyorlar diye dusunmekten kendimi alamadim. o zamanlar da uslup konusu hep gundeme geldi, ama degisen birsey olmadi. Bir nevi sizde oyle yapmissiniz. Sudoku uzerinde ilmi bir calismam yok, ilgilenmiyorum da ama sudoku gibi pekala matematiksel olabilecek bir enstrumanin zaman israfi ve/veya bir dinmis gibi lanse edilmesi de uygun bir davranis degildir. Sudoku'yu cozmek icin gelistirilen sayilar teorisi mantiklarini ve algoritmalarini gorseniz boyle bir enstrumanin ne kadar faydali oldugunu soylersiniz.

Ama benim esas belirtmek istedigim nokta bu degildi. Esasen ozellikle pure matematik alaninda calisan bircok arkadasimizin yaptiklari/cozdukleri problemlerin ne ise yaradiklarini bilmediklerini belirtmek istemistim. Yurtdisinda yasiyorum, buraya postdoc icin gelen bir arkadasin yazdigi bir makaleyi anlamaya calisirken, 'tamam da, simdi bu sonuc ne ise yariyor?' diye sormustum. cevap olarak 'bilmiyorum, ama problemi dogru cozmusum' dedi. belki yarin gruba uye bir grup hocamizin karsisina 'docent' adayi olarak gelecektir bu arkadas. Mevzuu uzun kisa kesiyoum.

Kisacasi, sudoku'yu kucumsemektense; boyle bir enstrumani kullanarak mesela, okullarda matematigi nasil sevdirebiliriz? veya acaba belli sudokulari cozen ogrencilerin analitik dusunceleri gelisiyor mu? veya ne bileyim, 16x16 sudoku'yu bir bilgisayara cozdurmek icin uygun bir algoritma nasil yazilir? vs. turu sorular uzerine yogunlassak herhalde daha iyi olacaktir. Dedim ya, konu hakkinda bilgim cok yuzeysel oldugu halde bunlar aklima geldi. Daha dusunulse cok sey yazilabilir.

Yeniden sizi kirdim ise ozur dilerim. Kalin saglicakla.

Orcun.

________________________________
 From: "meulkudas at mynet.com" <meulkudas at mynet.com>
To: yamanorcun at yahoo.com 
Cc: turkmath at listweb.bilkent.edu.tr 
Sent: Monday, January 23, 2012 11:15 AM
Subject: Ynt: Re: [Turkmath:8139] Ynt:  sudoku

Sayın Orcun
Karşı görüşte olmak, beirilen fikirlere katılmamak, hatta eleştiri yapmak
gayet doğaldır. Ben kendi fikrimi arz ettim, kimsenin benimle hemfikir
olmasını beklemeksizin. Sizin farklı görüşünüzü, itirazınızı saygı ile karşılarım.
Ancak, ancak ve ancak şunu da belirmek durumundayım ki 
yanıtınızdaki üslup paylaşım ortamımız Turkmath'a
asla yakışmıyor.
Üstelik mundar yanlış, Türkçe vokabulerde bir sözcük yok.
Murdar demek istiyorsunuz, onu da beceremiyorsunuz.
Arapça kökenli  Osmanlıca bu kelimenin anlamı, pis, kokuşmuş, çok pis çok kokuşmuş.
Bunu bilerek söylüyorsanız bir türlü bilmeden lugat paralıyor iseniz bir başka türlü edep-dışı
tavır sergilemiş oluyorsunuz. Yazık, çok
yazık.
Gene de emekli/emektar bir öğretim üyesi olarak yanlışlığınızın
toyluğunuzdan kaynaklandığı önsavı ile sizi bağışlıyorum.
Esenlikler dileklerimle ...

>----- Özgün İleti -----
>Kimden : yamanorcun at yahoo.com
>Kime : "meulkudas at mynet.com" <meulkudas at mynet.com>, "muhammed.uludag at gmail.com" <muhammed.uludag at gmail.com>
>Cc : "turkmath at listweb.bilkent.edu.tr" <turkmath at listweb.bilkent.edu.tr>
>Gönderme tarihi : 23 Ocak 2012 Pazartesi 00:14
>Konu : Re: [Turkmath:8139] Ynt:  sudoku
>
>
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 ﬁll 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/20120123/0d85fdd9/attachment-0001.htm>