{"id":1546,"date":"2011-06-01T00:16:07","date_gmt":"2011-05-31T22:16:07","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=1546"},"modified":"2011-06-01T00:16:07","modified_gmt":"2011-05-31T22:16:07","slug":"bez-cyfr","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2011\/06\/01\/bez-cyfr\/","title":{"rendered":"Bez cyfr"},"content":{"rendered":"

Ka\u017cdy pocz\u0105tkuj\u0105cy\u00a0amator sudoku szybko zauwa\u017ca, \u017ce im mniej cyfr jest na pocz\u0105tku ujawnionych, tym trudniejsze zadanie. To wprawdzie nie regu\u0142a, ale zazwyczaj tak jest. Ciekawscy, zw\u0142aszcza ci z matematycznym zaci\u0119ciem,\u00a0 z czasem zadaj\u0105 sobie pytanie: ile cyfr najmniej mo\u017cna ujawni\u0107, aby zadanie mia\u0142o jedno rozwi\u0105zanie? Japo\u0144scy mi\u0142o\u015bnicy sudoku ju\u017c przed 20 laty zauwa\u017cyli, \u017ce prawdopodobnie nie da si\u0119 zej\u015b\u0107 poni\u017cej siedemnastu. „Siedemnastki” pojawia\u0142y si\u0119 jednak w prasie\u00a0bardzo rzadko i raczej jako kurioza, poniewa\u017c zwykle\u00a0s\u0105 rozrywkowe inaczej, czyli horrendalnie trudne.\u00a0A je\u015bli w miar\u0119 \u0142atwe, to tak\u017ce trudne, ale do u\u0142o\u017cenia.<\/p>\n

Gdy sudoku przed sze\u015bciu laty eksplodowa\u0142o na \u015bwiecie, 17-cyfrow\u0105 granic\u0119 powt\u00f3rnie odkryto na Zachodzie i pr\u00f3bowano j\u0105 przekroczy\u0107. Pojawi\u0142 si\u0119 wi\u0119c tzw. problem 16 cyfr, z kt\u00f3rym programi\u015bci zmagali si\u0119 r\u00f3\u017cnymi metodami. Jedni szukali 16-cyfrowego diagramu wsp\u00f3lnymi si\u0142ami w ramach projektu przetwarzania rozproszonego BOINC<\/a>, inni zbierali „siedemnastki” w nadziei, \u017ce uda si\u0119 zej\u015b\u0107 oczko ni\u017cej, modyfikuj\u0105c kt\u00f3r\u0105\u015b z nich. Za czo\u0142owego kolekcjonera uchodzi Gordon Royle, profesor matematyki z University of Western Australia w Perth, kt\u00f3ry w ci\u0105gu paru lat zgromadzi\u0142 blisko 50 tysi\u0119cy ca\u0142kiem<\/strong> r\u00f3\u017cnych siedemnastek z jednym rozwi\u0105zaniem. Na stronie pana profesora<\/a> mo\u017cna je wszystkie pobra\u0107, a przy okazji zapozna\u0107 si\u0119 z niekt\u00f3rymi aspektami teoretycznymi zagadnienia. Zapewne najciekawszym efektem tej pasji jest szesnastka z dwoma<\/strong> rozwi\u0105zaniami:<\/p>\n

\"\"<\/a><\/p>\n

Wbrew pozorom rozwi\u0105zywanie tej „bli\u017aniaczki” nie jest trudne, cho\u0107 je\u017celi skorzysta\u0107 z\u00a0solvera Andrew Stuarta<\/a>, to oka\u017ce si\u0119, \u017ce pokr\u0119tnych metod\u00a0pod koniec zmaga\u0144 nie spos\u00f3b unikn\u0105\u0107. Mimo to nie stosuj\u0105c ich, ani\u00a0te\u017c pr\u00f3bowania i b\u0142\u0105dzenia, dotar\u0142em do\u015b\u0107 \u0142atwo do celu,\u00a0wi\u0119c chyba solver przesadza.<\/p>\n

Podobno to jedyna znana szesnastka z dwoma rozwi\u0105zaniami – z dok\u0142adno\u015bci\u0105 do przekszta\u0142ce\u0144 diagramu (przestawienia rz\u0119d\u00f3w, sektor\u00f3w, liczb itp.), w wyniku kt\u00f3rych powstaj\u0105 inne szesnastki, ale nie ca\u0142kiem<\/strong> inne, czyli jakby zmodyfikowane kopie.\u00a0 Mam w\u0105tpliwo\u015bci, bo przynajmniej jedna z innych znanych mi szesnastek wygl\u0105da na nale\u017c\u0105c\u0105 do innej rodzinki, czyli ca\u0142kiem<\/strong> inn\u0105 ni\u017c powy\u017csza. Ci\u0119\u017cko to sprawdzi\u0107, aby mie\u0107 pewno\u015b\u0107, bo rodzinka liczy\u00a01 218 998 108 160 diagram\u00f3w. Ale pr\u00f3by trwaj\u0105.<\/p>\n

Problem 16 cyfr pozostaje otwarty. Nikt nie udowodni\u0142, \u017ce 17 stanowi minimum. Tym niemniej wszyscy, kt\u00f3rzy zg\u0142\u0119biali to zagadnienie, zgodnie twierdz\u0105, i\u017c pole poszukiwa\u0144 zosta\u0142o\u00a0na tyle\u00a0dok\u0142adnie „przeorane”, \u017ce znalezienie szesnastki by\u0142oby sensacj\u0105 granicz\u0105c\u0105 z cudem.<\/p>\n

Natomiast nie jest cudem sudoku, w kt\u00f3rym na pocz\u0105tku w diagramie nie ma… ani jednej cyfry\u00a0– nie ma te\u017c jakichkolwiek pomocniczych symboli literowych lub cyfrowych, jak np. w wariancie killer<\/a>\u00a0– a mimo to jest tylko jedno rozwi\u0105zanie. Chodzi oczywi\u015bcie o niekt\u00f3re odmiany klasycznej \u0142amig\u0142\u00f3wki\u00a0– takie, w kt\u00f3rych kluczem do rozwi\u0105zania s\u0105 zale\u017cno\u015bci mi\u0119dzy cyframi. Inaczej m\u00f3wi\u0105c, zamiast konkretnych cyfr mo\u017cna np. wskaza\u0107, w kt\u00f3rym z dw\u00f3ch s\u0105siednich p\u00f3l powinna pojawi\u0107 si\u0119 wi\u0119ksza albo oznaczy\u0107 jedn\u0105 „niewidk\u0119” jako sum\u0119 kilku innych. Moim zdaniem bezcyfrowe sudoku s\u0105 najciekawsze w tym drugim przypadku, czyli w odmianie strza\u0142kowej, o kt\u00f3rej wspomina\u0142em w dw\u00f3ch poprzednich wpisach. Oto przyk\u0142ad takiego zadania, kt\u00f3re na pierwszy rzut oka mo\u017ce si\u0119 wyda\u0107 nierozwi\u0105zywalne:<\/p>\n

\"\"<\/a><\/p>\n

Przypominam zasady:
\n– regu\u0142a podstawowa: r\u00f3\u017cne cyfry (od 1 do 9) powinny znale\u017a\u0107 si\u0119 w ka\u017cdym rz\u0119dzie, ka\u017cdej kolumnie i w ka\u017cdym sektorze 3×3 obwiedzionym grub\u0105 lini\u0105.
\n– regu\u0142a dodatkowa: ka\u017cda cyfra w polu z k\u00f3\u0142kiem powinna by\u0107 r\u00f3wna sumie cyfr w polach, kt\u00f3re przecina strza\u0142ka wychodz\u0105ca z k\u00f3\u0142ka.<\/p>\n

W rozwi\u0105zaniu wystarczy poda\u0107 cztery cyfry w rogach diagramu.<\/p>\n

Komentarze z prawid\u0142owymi<\/strong> rozwi\u0105zaniami uwalniane s\u0105 wieczorem w przeddzie\u0144 kolejnego wpisu. Wpisy pojawiaj\u0105 si\u0119 co 3-4 dni.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Ka\u017cdy pocz\u0105tkuj\u0105cy\u00a0amator sudoku szybko zauwa\u017ca, \u017ce im mniej cyfr jest na pocz\u0105tku ujawnionych, tym trudniejsze zadanie. To wprawdzie nie regu\u0142a, ale zazwyczaj tak jest. Ciekawscy, zw\u0142aszcza ci z matematycznym zaci\u0119ciem,\u00a0 z czasem zadaj\u0105 sobie pytanie: ile cyfr najmniej mo\u017cna ujawni\u0107, aby zadanie mia\u0142o jedno rozwi\u0105zanie? Japo\u0144scy mi\u0142o\u015bnicy sudoku ju\u017c przed 20 laty zauwa\u017cyli, \u017ce prawdopodobnie […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/1546"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=1546"}],"version-history":[{"count":35,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/1546\/revisions"}],"predecessor-version":[{"id":1592,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/1546\/revisions\/1592"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=1546"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=1546"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=1546"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}