Mistrzostwa Sudoku
W połowie minionego roku, gdy o epidemii wypełniania diagramów 9×9 dziewięcioma cyframi było już głośno, ale nie osiągnęła ona jeszcze kulminacji, w wydanym przez Politykę zeszycie „Sudoku na wakacje”, stanowiącym zbiorek kilkudziesięciu łamigłówek, zamieszczone zostało jedno zadanie specjalne – eliminacyjne do I Mistrzostw Polski. Uporało się z nim, nadsyłając poprawne rozwiązanie, blisko tysiąc osób. To dużo, jeśli uwzględnić fakt, że zadanie było benedyktyńskie – pierwszy w Polsce wariant maksi, czyli diagram 16×16 – zmierzyli się z nim tylko najwytrwalsi z największych fanów. Potem był drugi etap eliminacji (internetowy) i finał w redakcji Polityki, do którego awansowały 62 osoby. Mistrzem Polski został informatyk z Warszawy Michał Karwański. W marcu we Włoszech rozegrano I. Mistrzostwa Świata, w których nasz as, zajmując 10 miejsce, otarł się o awans do finałowej dziewiątki.
Niemal bez echa przeszły drugie… I Mistrzostwa Świata, zorganizowane na innej, pomysłowej zasadzie. Ich uczestnicy… grali w sudoku. Eliminacje odbywały się online i polegały na równoczesnym rozwiązywaniu przez 2, 3 lub 4 osoby tego samego zadania na tym samym diagramie. Ściślej, każdy zawodnik obserwował na swoim monitorze kopię wspólnego diagramu i każdemu wskakiwały cyferki, którymi punktowali przeciwnicy. Kto pierwszy wpisał właściwą cyfrę w dane pole, zdobywał jeden punkt; błąd kosztował utratę 2 punktów. Zwyciężał, kto uzbierał więcej punktów, czyli był szybszy i miał trochę szczęścia. Program sędziujący zabezpieczał przed nieuczciwą grą (korzystanie z programów do rozwiązywania) – wpisując cyfrę poprawną, ale wziętą z sufitu, czyli nie wynikającą bezpośrednio z logicznej analizy aktualnej sytuacji, automatycznie wypadało się z gry. Zabawa przyjemna i emocjonująca – nadal można jej zasmakować na stronie organizatora Mistrzostw, szwedzkiej firmy Yooba, specjalizującej się w opracowywaniu gier i łamigłówek online. Najlepsi w internetowych eliminacjach rozegrali 15 października br. w Londynie finał, który składał się z serii pojedynków – najpierw w trójkach, a w końcówce w parach. Dominowała młodzież, wśród której znalazł się 19-letni student AGH w Krakowie Jan Mrozowski. W rozstrzygającym o zwycięstwie starciu nasz faworyt uległ 17-letniej Holenderce Aniek Huijsman. Trzecie miejsce zajął Raffael Buff ze Szwajcarii, a czwarte 16-latek, Szwed Hans Edward Genow. Wielce osobliwa była nagroda dla zwyciężczyni – wycieczka do niezwykłego obiektu, przedstawionego na zdjęciu. Pora na zagadkę: co to jest i gdzie się znajduje? Kto nie wie albo nie przypomina sobie, tego być może naprowadzi na odpowiedź informacja, że obiekt ten co roku wygląda nieco inaczej.
Szaleństwo sudoku za nami, ale łamigłówka trzyma się mocno. Tu i ówdzie zadomowiła się w działach rozrywek umysłowych jako dopełnienie krzyżówki. Stadami gości na łamach wydawnictw wyłącznie lub głównie jej poświęconych – książek i paru pisemek. Sądząc z ich nakładów, mamy w Polsce 60-80 tysięcy sudokowiczów. Co jednak istotniejsze, przynajmniej dla mnie, sudoku wyszlachetniało – doczekało się wielu ciekawych odmian wymagających bardziej wszechstronnego ruszania głową a także nobilitowali je matematycy, którzy zaczęli mu się wnikliwie przyglądać. Najbardziej frapującym zagadnieniem, dotyczącym klasycznego wariantu 9×9, jest tzw. „problem siedemnastki”: czy można umieścić na początku w diagramie mniej niż 17 cyfr tak, by było tylko jedno rozwiązanie? Wprawdzie jak dotąd nikt nie udowodnił, że nie jest to możliwe, ale z drugiej strony przeanalizowanie wszystkich diagramów z 16 cyframi na najszybszym komputerze zajęłoby dziś kilka tysięcy lat. Całkowicie różnych przykładów z 17 cyframi i jednym rozwiązaniem australijski matematyk Gordon Royle zebrał blisko 40 tysięcy. Przy okazji udało mu się ułożyć jedyną znaną jak dotąd łamigłówkę z 16 ujawnionymi cyframi, mającą tylko dwa rozwiązania. Jeśli ktoś z Państwa nie wypełniał jeszcze tego diagramu, zapraszam do zabawy. Zadanie nie jest trudne, ale tylko dopóki nie zacznie się „rozdwajać”. Końcowe etapy wymagają stosowania metody prób i błędów oraz korzystania z „łańcuszkowego” sposobu eliminacji położenia kilku cyfr.
W świątecznym numerze Polityki nastąpi reaktywacja sudoku, czyli zamieszczone będą zadania eliminacyjne do II Mistrzostw Polski. Drugi (internetowy) etap eliminacji w lutym, finał w marcu 2007 roku w redakcji Polityki. Na najlepszych czekają atrakcyjne nagrody. Sponsorem Mistrzostw jest Altkom Akademia S.A.
Po rozwiązaniu zadań z wydania świątecznego diagramami będzie można przyozdobić choinkę, nie zapominając oczywiście o uprzednim wypełnieniu i wysłaniu do redakcji kuponu konkursowego.
Komentarze
Czy w 16-liczbowym sudoku na pewno nie ma błędu, bo coś mi się wydaje, ze ma ono więcej niż dwa rozwiązania?
zadanie logiczne, nie tylko sudoku, które wymaga prób i błędów zawsze uważam za „niehonorowe”
Koryguję (i kryguję) się. Rozwiązania są jednak rzeczywiście jedynie dwa. Tylko, że pod koniec bardzo trudno je wyłuskać. Stąd były moje (nieuzasadnione) wątpliwości.
A co do komentarza fajki2: wydaje mi się, że przynajmniej połowa zadań lolgicznych jest „niehonorowa”, bo wymaga, chocby w niewielkim stopniu, próbowania i błądzenia. Uważam zresztą, że także w tym tkwi ich… urok.
Kłóciłbym się z tym stwierdzeniem, że po wpisaniu cyfry wziętej z sufitu od razu wypadało się z gry. Spróbowałem w jakieś pole wpisywać kolejno cyfry i za poprawnie wpisaną miałem punkt, więc nie wiem skąd macie taką informację. Osobiście również nie widziałem, aby ktoś był zdyskwalifikowany podczas gry. Po drugie granie programem nie jest opłacalne, gdyż cały pojedynek między czterema graczami trwa średnio minutę albo mniej.
Mistrzu Janosławie, informacji o wypadaniu z gry po wpisaniu cyfry z sufitu nie wziąłem z sufitu. Korzystałem z informacji podanej na stronie Yooby:
„The game monitors if a player enters numbers in an inconsistent or illogical order. The game also tracks any deviation from the general pattern of playing. You can rest assured that there is no room for cheating ”
oraz z opisu takiego przypadku na forum sudokowym (angielskim lub holenderskim – niestety, nie pamiętam na którym). Niewykluczone, że był to przypadek incydentalny.
Pozdrawiam
mp
Witaj,
mam pytanie czy mozna kupić jeszcze w kioskach ten numer Polityki z kuponami eliminacyjnymi? A moze mozna zamowic archiwalny świąteczny numer , tylko czy nie jest już za pozno na wysylanie tych kuponow?
Dziekuje z gory za odpowiedz i pozdrawia.
Jaro
Nie wiem czy można jeszcze kupić, ale termin nadsyłania rozwiązań jest do 10 stycznia ( nie wiem czy decyduje data stempla czy przysłania, bo nie jest napisane, ale raczej to pierwsze :] ). Więc nawet jak zdążysz kupić to musisz się bardzo spieszyć. Jeśli chodzi o archiwalny numer to możliwe, że na jakimś bazarku uda się kupić stary numer. Chociaż dokładnie nie wiem z jakim przedawnieniem gazety trafiają tam na stoiska.
Ze swojej strony mogę obiecać, że redakcja nie będzie zbyt rygorystyczna, jeśli chodzi o termin nadsyłania rozwiązań. Uwzględniamy kondycję poczty, która nie jest ostatnio najlepsza.
Poza nabyciem archiwalnego numeru w redakcji – najlepiej, jeśli to mozliwe, osobiście, bo mimo wszystko czasu jest niewiele – pozostaje sposób, który podpowiedział Janosław.
Pozdrawiam
mp
czy w sudoku NPK nie można umieszczać koło siebie 1 i 9?
po drugie: czy ta zasada działa przez granice kwadratów? Mnie się wydaje to oczywistym, ale jednak.
Dziękuję.
1 i 9 mogą sąsiadować – wszak to nie kolejne liczby (zasada nie działa „w kółko”).
Oczywiście zasada dotyczy całego diagramu, a więc także sąsiednich pól należących do sąsiednich kwadratów 3×3.
Pozdrawiam
mp
ojej :0
więc już wiem o co chodzi.
dziękuuuuuujęęęęęę!!!!
Ponieważ minął już czas na nadsyłanie rozwiązań, więc pora na ich prezentację, podaję przykładowe solucje.
Legenda: + miejsce, – wiersz, | kolumna, # kwadrat/puzzle, S strzelam
[w nawiasach wiersz i kolumna]
Kolejne cyfry SUDOKU X:
28 + [2,7] 1
29 – [5,1] 3
30 – [6,8] 3
31 | [6,1] 4
32 | [8,3] 5
33 – [2,8] 6
34 – [6,6] 6
35 – [7,4] 6
36 | [1,2] 6
37 | [7,2] 9
38 + [6,4] 9
39 + [6,5] 1
40 – [4,2] 1
41 | [1,1] 1
42 | [8,9] 1
43 # [9,8] 2
44 – [4,6] 8
45 + [5,5] 5
46 + [9,1] 7
47 – [3,2] 7
48 – [4,4] 7
49 – [5,3] 7
50 – [8,6] 7
51 | [1,7] 7
52 – [5,2] 8
53 | [1,3] 8
54 + [3,7] 2
55 + [4,7] 5
56 + [4,8] 4
57 + [4,9] 2
58 – [8,4] 3
59 | [2,9] 4
60 – [2,6] 9
61 | [9,9] 9
62 # [1,8] 9
63 # [8,5] 9
64 + [1,9] 3
65 + [3,9] 8
66 + [8,8] 8
67 + [9,5] 8
68 – [8,1] 2
69 – [3,6] 3
70 | [3,8] 5
71 – [7,1] 8
72 + [3,4] 1
73 + [9,4] 5
74 + [9,6] 1
75 – [1,6] 5
76 S [1,4] 2
77 + [1,5] 4
78 + [5,4] 4
79 + [5,6] 2
80 + [7,5] 2
81 + [7,6] 4
Kolejne cyfry Puzzle:
24 – [9,6] 3
25 # [2,5] 4
26 # [4,7] 4
27 # [7,6] 4
28 | [5,3] 5
29 | [7,7] 5
30 | [1,9] 5
31 # [3,2] 5
32 – [7,9] 9
33 – [9,7] 9
34 # [5,2] 9
35 – [1,2] 1
36 – [6,9] 1
37 | [9,1] 1
38 | [4,4] 1
39 | [8,5] 1
40 | [5,8] 1
41 – [6,1] 3
42 – [6,2] 4
43 – [8,9] 4
44 | [3,4] 4
45 – [8,1] 5
46 # [7,5] 6
47 + [6,5] 8
48 – [6,3] 6
49 – [8,7] 6
50 | [2,2] 6
51 | [1,4] 6
52 | [5,6] 6
53 # [4,1] 6
54 | [8,2] 7
55 | [6,7] 7
56 – [5,7] 8
57 | [7,4] 8
58 | [8,8] 8
59 + [2,7] 2
60 + [5,4] 2
61 + [6,6] 2
62 + [8,3] 2
63 + [9,4] 7
64 + [9,8] 2
65 – [7,1] 2
66 | [3,9] 2
67 – [7,8] 7
68 S [1,3] 7
69 + [1,6] 8
70 + [3,6] 7
71 – [4,9] 7
72 | [2,1] 7
73 – [2,9] 8
74 – [3,1] 8
75 – [4,3] 8
76 S [2,3] 3
77 + [2,8] 9
78 + [3,3] 9
79 + [3,5] 3
80 + [4,5] 9
81 + [4,8] 3
Kolejne cyfry NPK:
16 + [2,7] 5
17 + [8,3] 6
18 + [8,5] 5
19 – [6,4] 8
20 – [8,8] 8
21 S [2,2] 3
22 + [2,5] 4
23 + [6,5] 1
24 – [6,6] 4
25 # [5,4] 5
26 # [4,6] 6
27 + [4,8] 1
28 – [3,2] 5
29 | [1,6] 5
30 | [6,9] 5
31 – [6,2] 6
32 | [3,5] 6
33 – [6,8] 7
34 | [1,4] 7
35 + [5,9] 3
36 – [1,7] 3
37 – [8,1] 3
38 – [3,8] 4
39 – [5,7] 6
40 – [7,4] 6
41 | [3,7] 8
42 # [5,8] 9
43 + [1,8] 6
44 + [3,9] 1
45 + [5,6] 2
46 + [8,7] 1
47 | [1,5] 2
48 – [7,2] 4
49 – [9,4] 4
50 | [1,3] 4
51 # [5,1] 4
52 – [7,8] 5
53 – [9,1] 5
54 – [9,9] 6
55 – [3,3] 7
56 # [2,9] 7
57 | [1,1] 8
58 | [5,2] 8
59 – [1,9] 9
60 – [2,3] 9
61 – [3,4] 9
62 – [4,5] 9
63 + [1,2] 1
64 + [3,1] 2
65 + [3,6] 3
66 + [4,1] 7
67 + [4,2] 2
68 + [4,4] 3
69 + [5,3] 1
70 + [7,1] 1
71 + [7,3] 8
72 + [7,5] 3
73 + [7,6] 9
74 + [7,7] 7
75 + [7,9] 2
76 + [9,2] 7
77 + [9,3] 2
78 + [9,5] 8
79 + [9,6] 1
80 + [9,7] 9
81 + [9,8] 3
po co komu rozwiązania ze strzelaniem?
Większość trudniejszych sudoku bez strzelania jest nierozwiązywalnych, tylko te łatwe i średnio trudne daje się rozwiązać forsownie. Czasem występuje kilka zagnieżdżonych poziomów prób i błędów, co jest najciekawsze. Odnośnie zadań z 2 MP, to spróbuję wyjaśnić czemu strzelam. W Sudoku X są dwa rozwiązania, więc ostanie cyfry mogą być zamiennie 2 lub 4. Podobnie w Puzzle, ale tu są aż 2 warianty (7 lub 8 oraz 3 lub 9) czyli 4 rozwiązania (2×2=4), natomiast NPK bez strzelania się nie da rozwiązać, gdybyśmy w polu [2,2] wpisali 4, to szybciutko dochodzimy do sprzeczności, więc to wg mnie jest optymalny strzał, po którym wszystko już idzie forsownie najprostszymi elementarnymi metodami. Może to się powinno nazywać inaczej, to bardzo proszę o fachowe wyjaśnienie, bo jestem amatorem i sam sobie powymyślałem te nazwy metod rozwiązywania. 🙂
W uzupełnieniu tylko dodam, po konsultacji z mądrzejszymi ode mnie mistrzami sudoku, że w polu [2,2] nie może być 4, bo np. w kwadracie nie będzie możliwości wpisania 5, więc w zasadzie 3 nie jest strzałem, tylko logiczną konsekwencją, czyli NPK rozwiązuje się BEZ STRZELANIA. 🙂
„Większość trudniejszych sudoku bez strzelania jest nierozwiązywalnych, tylko te łatwe i średnio trudne daje się rozwiązać forsownie.”
Oczywiście ciężko mi powiedzieć co znaczy „trudniejszych” w tym wypadku, tak samo nie wiem o jaką większość chodzi – czy tych drukowanych czy też wszystkich możliwych diagramów. Natomiast wiem, że stwierdzanie, że czegoś nie da się rozwiązać wnioskowaniem jest dosyć ryzykowne, ponieważ możesz nie znać wszystkich sposobów wnioskowania i o tym nie wiedzieć. Co zresztą widać w prezentowanym zapisie, w którym nie da się, a przynajmniej nie widzę jak, zapisać wszystkich sposobów wnioskowania chociażby mi znanych. Zresztą jak sam widzisz NPK dało się rozwiązać co słusznie zauważył karwer na forum Sfinksa.
Co do „optymalnego strzału” to trzeba się zdecydować:
– albo strzelasz czyli nie masz pojęcia jak szybko dojdziesz do sprzeczności, w szczególności jeśli masz szczęście nie dojdziesz do niej wcale
– albo przemyślałeś sprawę i wiesz, że dojdziesz w danym miejscu do sprzeczności – to nie jest już strzał. Bo skoro wiesz to nie strzelasz.
Oczywiście nawet strzelając można strzelać źle lub dobrze. Twoje strzały były z tych „dobrych”. Ale jak widać niepotrzebne. I możesz mi wierzyć, że na pewno nie większość, a wręcz niewiele z zadań drukowanych w polskich pismach wymaga strzelania (zresztą jak sam pisałem – tak naprawdę to nie wiem czy wymaga – po prostu ja muszę strzelić). Pod warunkiem, że mają jednoznaczne rozwiązania.
Natomiast nadal nie widziałem odpowiedzi na moje pytanie: po co komu rozwiązania ze strzelaniem? Pytanie dotyczy głównie NPK, bo skoro pozostałe zadania miały niejednoznaczne rozwiązania to logiczne jest, że żadnego nie da się wywnioskować krok po kroku
Tomku, zgadzam się, co do zbyt pochopnej mojej wypowiedzi, którą zacytowałeś. Zbyt ogólnikowo ją sformułowałem i źle uzasadniłem. Miałem na myśli tylko wymienione elementarne sposoby wnioskowania, czyli szukania pojedynczej cyfry w polu, wierszu. kolumnie i kwadracie. Istnieje wiele innych zaawansowanych sposobów wnioskowania, które mogą eliminować konieczność strzelania. W mojej metodzie rozwiązywania ograniczyłem się do tych kilku podstawowych metod i wszystko pozostałe załatwiam strzelaniem, możliwe, że to jest nikomu niepotrzebne. Jeśli znajdę na to siły, to w przyszłości będę się uczył kolejnych sposobów wnioskowania. W przypadku tego konkretnego NPK, jak wyjaśnił Karwer, 3 w polu [2,2] można wywnioskować i w rzeczywistości nie jest strzałem, więc po zastąpieniu literki S wnioskowaniem np. o nazwie „analiza Karwera” otrzymamy przykładowe rozwiązanie bez strzelania. Obiecuję, że nigdy więcej nie zaprezentuję rozwiązania ze strzelaniem. Chętnie zobaczę inne rozwiązania z opisami większej ilości metod wnioskowania. 🙂
No z ta „analiza Karwera” to przesadziles… Juz teraz to na pewno Tomek bedzie mial ze mnie ubaw 🙂
Karwer, przepraszam, ale jakoś musiałem to nazwać, a Twoje wnioskowanie bardzo mi się spodobało. 🙂
Tomek twierdzi, że jeśli „wiesz, że dojdziesz w danym miejscu do sprzeczności – to nie jest już strzał”, więc może by to wnioskowanie nazwać „już nie strzał Tomka”. 🙂
P.S. Sudoku Players’ Forums zawiera dużo odnośników do opisów zaawansowanych metod rozwiązywania sudoku, można postudiować w długie zimowe wieczory. 🙂