Reklama
Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2
Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko

1.06.2011
środa

Bez cyfr

1 czerwca 2011, środa,

Każdy początkujący amator sudoku szybko zauważa, że im mniej cyfr jest na początku ujawnionych, tym trudniejsze zadanie. To wprawdzie nie reguła, ale zazwyczaj tak jest. Ciekawscy, zwłaszcza ci z matematycznym zacięciem,  z czasem zadają sobie pytanie: ile cyfr najmniej można ujawnić, aby zadanie miało jedno rozwiązanie? Japońscy miłośnicy sudoku już przed 20 laty zauważyli, że prawdopodobnie nie da się zejść poniżej siedemnastu. „Siedemnastki” pojawiały się jednak w prasie bardzo rzadko i raczej jako kurioza, ponieważ zwykle są rozrywkowe inaczej, czyli horrendalnie trudne. A jeśli w miarę łatwe, to także trudne, ale do ułożenia.

Gdy sudoku przed sześciu laty eksplodowało na świecie, 17-cyfrową granicę powtórnie odkryto na Zachodzie i próbowano ją przekroczyć. Pojawił się więc tzw. problem 16 cyfr, z którym programiści zmagali się różnymi metodami. Jedni szukali 16-cyfrowego diagramu wspólnymi siłami w ramach projektu przetwarzania rozproszonego BOINC, inni zbierali „siedemnastki” w nadziei, że uda się zejść oczko niżej, modyfikując którąś z nich. Za czołowego kolekcjonera uchodzi Gordon Royle, profesor matematyki z University of Western Australia w Perth, który w ciągu paru lat zgromadził blisko 50 tysięcy całkiem różnych siedemnastek z jednym rozwiązaniem. Na stronie pana profesora można je wszystkie pobrać, a przy okazji zapoznać się z niektórymi aspektami teoretycznymi zagadnienia. Zapewne najciekawszym efektem tej pasji jest szesnastka z dwoma rozwiązaniami:

Wbrew pozorom rozwiązywanie tej „bliźniaczki” nie jest trudne, choć jeżeli skorzystać z solvera Andrew Stuarta, to okaże się, że pokrętnych metod pod koniec zmagań nie sposób uniknąć. Mimo to nie stosując ich, ani też próbowania i błądzenia, dotarłem dość łatwo do celu, więc chyba solver przesadza.

Podobno to jedyna znana szesnastka z dwoma rozwiązaniami – z dokładnością do przekształceń diagramu (przestawienia rzędów, sektorów, liczb itp.), w wyniku których powstają inne szesnastki, ale nie całkiem inne, czyli jakby zmodyfikowane kopie.  Mam wątpliwości, bo przynajmniej jedna z innych znanych mi szesnastek wygląda na należącą do innej rodzinki, czyli całkiem inną niż powyższa. Ciężko to sprawdzić, aby mieć pewność, bo rodzinka liczy 1 218 998 108 160 diagramów. Ale próby trwają.

Problem 16 cyfr pozostaje otwarty. Nikt nie udowodnił, że 17 stanowi minimum. Tym niemniej wszyscy, którzy zgłębiali to zagadnienie, zgodnie twierdzą, iż pole poszukiwań zostało na tyle dokładnie „przeorane”, że znalezienie szesnastki byłoby sensacją graniczącą z cudem.

Natomiast nie jest cudem sudoku, w którym na początku w diagramie nie ma… ani jednej cyfry – nie ma też jakichkolwiek pomocniczych symboli literowych lub cyfrowych, jak np. w wariancie killer – a mimo to jest tylko jedno rozwiązanie. Chodzi oczywiście o niektóre odmiany klasycznej łamigłówki – takie, w których kluczem do rozwiązania są zależności między cyframi. Inaczej mówiąc, zamiast konkretnych cyfr można np. wskazać, w którym z dwóch sąsiednich pól powinna pojawić się większa albo oznaczyć jedną „niewidkę” jako sumę kilku innych. Moim zdaniem bezcyfrowe sudoku są najciekawsze w tym drugim przypadku, czyli w odmianie strzałkowej, o której wspominałem w dwóch poprzednich wpisach. Oto przykład takiego zadania, które na pierwszy rzut oka może się wydać nierozwiązywalne:

Przypominam zasady:
– reguła podstawowa: różne cyfry (od 1 do 9) powinny znaleźć się w każdym rzędzie, każdej kolumnie i w każdym sektorze 3×3 obwiedzionym grubą linią.
– reguła dodatkowa: każda cyfra w polu z kółkiem powinna być równa sumie cyfr w polach, które przecina strzałka wychodząca z kółka.

W rozwiązaniu wystarczy podać cztery cyfry w rogach diagramu.

Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 10

Dodaj komentarz »
  1. 8|9

    1|2

  2. Podłe to drugie, przy czym cyfry z rogów można uzyskać tak w 2/3 rozwiązywania:
    8912

  3. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  4. Gorne rogi – 8 i 9
    dolne – 1 i 2
    a

  5. 89
    12

    A w pierwszym zadaniu wyszło mi więcej rozwiązań niż dwa. Pozdrawiam 🙂

    Mme Ola la :), il est impossible.
    To ja wstukam dwa, a Pani wskaże trzecie:

    1726XX345
    X3X457216
    564321XX7
    61X5X3724
    X432765X1
    257X1463X
    7X513246X
    42176XX53
    3X6X45172
    Zamiast X można wstawić 8 i 9 na dwa sposoby.
    Salut
    mp

  6. Rzeczywiście, il est impossible. Właśnie znalazłam błąd. Pozdrawiam 🙂

  7. 826537149
    741928563
    593641827
    985714236
    317256498
    462389715
    239175684
    674892351
    158463972

    Na pierwszy rzut oka zadanie wygląda na monstualnie trudne. A jednak można dość szybko dojść do rozwiązania i to wyłącznie „logicznymi” metodami, bez prób i błędów. Kluczowe jest przeanalizowanie drugiego wiersza.

  8. 826537149
    741928563
    593641827
    985714236
    317256498
    462389715
    239175684
    674892351
    158463972

    Zadanko dało mi trochę do wiwatu:) musiałem odłożyć je w połowie rozwiązane na cały dzień… z powodu braku czasu też, ale w końcu ‚pękło’ipoddało mi się 🙂

  9. Dla miłośników sudoku:
    http://www.technologyreview.com/blog/arxiv/27469/?p1=blogs
    udowodniono, z tego co rozumiem, że nie ma jednoznacznego rozwiązania dla 16 liczb podanych w diagramie sudoku.

    Istotnie, choć dowód nieelegancki.
    Elegancki – to by było coś (było kilka prób, ale w każdej znaleziono błąd).
    mp

css.php