Bez zalążka
We wszystkich (prawie wszystkich?) łamigłówkach diagramowych, polegających na wpisywaniu cyfr w kratki (ściślej: we wszystkie kratki), występuje zalążek. Zalążkiem nazywam przynajmniej kilka cyfr wpisanych w diagram na dobry początek, a tak naprawdę po to, aby rozwiązanie było jedno. Typowym przykładem jest sudoku, które zwykle zawiera na starcie nieco ponad 20 pól z cyframi, a co najmniej 17. Wszystko wskazuje na to, że mniej być nie może, a nikt nie wie dlaczego, tzn. nikt nie udowodnił, że 17 to rzeczywiście minimum.
Czy istnieją zadania bez zalążka? Inaczej mówiąc: czy można tak sformułować reguły zabawy, aby umieszczanie ileś tam cyfrowego zalążka nie było konieczne? Oto przykład, że jest to możliwe.
W każdy wielokąt (polimino) obejmujący N kratek należy wpisać N różnych liczb od 1 do N. Każde dwie kolejne liczby w wielokącie powinny znaleźć się w sąsiednich kratkach, czyli mających wspólny bok. Natomiast w całym diagramie jednakowe liczby nie mogą pojawić się w sąsiednich kratkach.
W rozwiązaniu można podać tylko sumę dziewięciu liczb na przekątnej łączącej lewy górny róg z prawym dolnym.
Komentarze
532713657, czyli 39
532713657
Idea /koncepcja /pomysł :
A gdyby w każde polimino rozmiaru N należało wpisać N kolejnych liter alfabetu?
Niekoniecznie zaczynając od litery „A”.
Widzę oczami wyobraźni długiego „węża” ciągnącego się przez sporą część diagramu…
5+3+2+7+1+3+6+5+7=39
Jedyne rozwiązanie:
5,4,2,3,1,2,5,3,4
2,3,1,6,5,3,4,2,5
1,5,2,3,4,1,2,1,6
3,4,1,7,6,5,3,4,7
2,3,4,8,1,4,2,3,1
1,2,1,9,2,3,1,8,2
3,4,3,4,3,5,6,7,3
2,1,2,1,2,4,1,5,4
1,2,3,4,1,3,2,6,7
Na przekątnej są liczby 5+3+2+5+1+9+6+5+7=43
@ Antyp1958
Domniemywam, że mamy tu problem z cyfrą „4” ze środkowego polimina 3×3: kwestia sąsiada z lewej?
39, przyjemnie się rozwiązuje. Przynajmniej dla mnie finałowy był centralny kwadrat 3×3: zaczynamy od 1 w środku i potem idziemy w dół i dalej w prawo, to determinuje resztę.
W poprzednim moim poście był błąd (sąsiadowały ze sobą dwójki), powinno być 5+3+2+7+1+3+6+5+7=39.
Inne: 532713657=39
5-3-2-7-1-3-6-5-7
Może to trochę musztarda po obiedzie, ale chciałem wnieść pewne sprostowanie do Pana stwierdzenia: „Typowym przykładem jest sudoku, które zwykle zawiera na starcie nieco ponad 20 pól z cyframi, a co najmniej 17. Wszystko wskazuje na to, że mniej być nie może, a nikt nie wie dlaczego, tzn. nikt nie udowodnił, że 17 to rzeczywiście minimum.” Okazuje się, że zostało udowodnione że nie uda się skonstruować zalążka sudoku o 16 cyfrach, który dałby jednoznaczne rozwiązanie. Co prawda dowód jest „komputerowy” tj. za pomocą superkomputera sprawdzono, że takiego początku nie ma, ale jest to jak najbardziej poprawny matematycznie dowód. Dokument w tej sprawie znajduje się na stronie https://arxiv.org/abs/1201.0749.
Cenna uwaga. Wiedziałem o tym. Ten „dowód” został także potwierdzony w programie BOINC http://sudoku.nctu.edu.tw/. Dowody komputerowe zawsze będą kontrowersyjne.
mp