Kakuro
Kakuro lub Kakkuro lub Kakoro ( japoński : カ ッ ク ロ ) to rodzaj łamigłówki logicznej , która jest często określana jako matematyczna transliteracja krzyżówki . Zagadki Kakuro regularnie pojawiają się w wielu publikacjach dotyczących zagadek matematycznych i logicznych na całym świecie. W 1966 roku Kanadyjczyk Jacob E. Funk, pracownik Dell Magazines , wymyślił oryginalną angielską nazwę Cross Sums i inne nazwy, takie jak Cross Addition były również używane, ale wydaje się, że japońska nazwa Kakuro, skrót od japońskiego kasan kurosu (加算 ク ロ ス, „dodatkowy krzyż”), zyskała powszechną akceptację i wydaje się, że łamigłówki są obecnie zatytułowane w ten sposób w większości publikacji. Popularność Kakuro w Japonii jest ogromna, ustępując jedynie Sudoku wśród słynnych puzzli logicznych Nikoli .
Kanoniczna łamigłówka Kakuro rozgrywana jest w siatce wypełnionych i przekreślonych komórek, odpowiednio „czarnych” i „białych”. Puzzle mają zwykle rozmiar 16 × 16, chociaż wymiary te mogą się znacznie różnić. Oprócz górnego rzędu i skrajnej lewej kolumny, które są całkowicie czarne, siatka jest podzielona na „wpisy” — linie białych pól — przez czarne pola. Czarne komórki zawierają ukośne ukośniki od lewego górnego do prawego dolnego rogu oraz liczbę w jednej lub obu połówkach, tak że każdy wpis poziomy ma numer w czarnej półkomórce bezpośrednio po lewej stronie, a każdy wpis pionowy ma numer w czarną półogniwo bezpośrednio nad nim. Liczby te, zapożyczając terminologię krzyżówkową, są powszechnie nazywane „wskazówkami”.
Celem łamigłówki jest wstawienie cyfry od 1 do 9 włącznie do każdej białej komórki, tak aby suma liczb w każdym wpisie odpowiadała powiązanej z nim wskazówce i aby żadna cyfra nie została zduplikowana w żadnym wpisie. To właśnie brak powielania umożliwia tworzenie puzzli Kakuro z unikalnymi rozwiązaniami. Podobnie jak Sudoku, rozwiązywanie łamigłówki Kakuro polega na badaniu kombinacji i permutacji . Istnieje niepisana zasada tworzenia łamigłówek Kakuro, że każda wskazówka musi mieć co najmniej dwie liczby, które się do niej sumują, ponieważ uwzględnienie tylko jednej liczby jest matematycznie trywialne podczas rozwiązywania łamigłówek Kakuro.
Co najmniej jeden wydawca nakłada ograniczenie, że danej kombinacji liczb można użyć tylko raz w każdej siatce, ale nadal sprzedaje łamigłówki jako zwykły Kakuro.
Niektórzy wydawcy wolą drukować swoje siatki Kakuro dokładnie tak, jak siatki krzyżówek, bez etykiet w czarnych polach i zamiast tego numerować wpisy, dostarczając oddzielną listę wskazówek, podobną do listy wskazówek do krzyżówek. (To eliminuje wiersz i kolumnę, które są całkowicie czarne). Jest to wyłącznie kwestia obrazu i nie wpływa ani na rozwiązanie, ani na logikę wymaganą do rozwiązania.
Omawiając łamigłówki i taktyki Kakuro, typowym skrótem odnoszącym się do wpisu jest „(wskazówka, cyframi) -w-(liczba komórek we wpisie, przeliterowana)”, na przykład „16 na dwa” i „25 -za pięć". Wyjątkiem jest to, co inaczej nazwano by „45-w-dziewiątej” — używa się po prostu „45”, ponieważ „-w-dziewięć” jest implikowane matematycznie (dziewięć komórek to najdłuższy możliwy wpis, a ponieważ nie można powielić cyfra musi składać się ze wszystkich cyfr od 1 do 9 jeden raz). Co ciekawe, zarówno „43-w-ósemce”, jak i „44-w-ósemce” są nadal często nazywane jako takie, mimo że sufiks „-w-ósemce” jest jednakowo sugerowany.
Techniki rozwiązywania
Techniki kombinatoryczne
Chociaż możliwe jest zgadywanie metodą brute-force, bardziej wydajnym podejściem jest zrozumienie różnych form kombinatorycznych, jakie mogą przybierać wpisy dla różnych par wskazówek i długości wpisów. Przestrzeń rozwiązania można zmniejszyć, rozwiązując dopuszczalne przecięcia sum poziomych i pionowych lub biorąc pod uwagę niezbędne lub brakujące wartości.
Te wpisy z wystarczająco dużymi lub małymi wskazówkami dla ich długości będą miały mniej możliwych kombinacji do rozważenia, a porównując je z wpisami, które je przecinają, można wyprowadzić właściwą permutację - lub jej część. Najprostszym przykładem jest sytuacja, w której 3 na 2 przecina 4 na 2: 3 na 2 musi składać się z „1” i „2” w jakiejś kolejności; 4-w-dwóch (ponieważ „2” nie można powielić) musi składać się z „1” i „3” w jakiejś kolejności. Dlatego ich przecięcie musi wynosić „1”, jedyną wspólną cyfrę.
Podczas rozwiązywania dłuższych sum istnieją dodatkowe sposoby na znalezienie wskazówek do zlokalizowania właściwych cyfr. Jedną z takich metod byłoby odnotowanie, gdzie kilka kwadratów razem ma wspólne możliwe wartości, eliminując w ten sposób możliwość, że inne kwadraty w tej sumie mogą mieć te wartości. Na przykład, jeśli dwie wskazówki 4 na 2 krzyżują się z dłuższą sumą, wówczas 1 i 3 w rozwiązaniu muszą znajdować się w tych dwóch kwadratach, a cyfr tych nie można użyć w innym miejscu tej sumy.
Podczas rozwiązywania sum, które mają ograniczoną liczbę zestawów rozwiązań, może to prowadzić do przydatnych wskazówek. Na przykład suma 30 w 7 ma tylko dwa zestawy rozwiązań: {1,2,3,4,5,6,9} i {1,2,3,4,5,7,8}. Jeśli jeden z kwadratów w tej sumie może przyjąć tylko wartości {8,9} (na przykład, jeśli wskazówką krzyżującą się jest suma 17 na 2), to nie tylko staje się to wskaźnikiem, który zestaw rozwiązań pasuje do tego suma, eliminuje możliwość, że jakakolwiek inna cyfra w sumie będzie jedną z tych dwóch wartości, nawet przed określeniem, która z dwóch wartości mieści się w tym kwadracie.
Innym przydatnym podejściem w bardziej złożonych łamigłówkach jest określenie, w którym kwadracie znajduje się cyfra, poprzez wyeliminowanie innych miejsc w sumie. Jeśli wszystkie przecinające się wskazówki sumy mają wiele możliwych wartości, ale można ustalić, że istnieje tylko jeden kwadrat, który może mieć określoną wartość, którą musi mieć dana suma, to niezależnie od innych możliwych wartości, na które pozwala suma przecinająca się, to przecięcie musi być izolowaną wartością. Na przykład suma 36 w 8 musi zawierać wszystkie cyfry z wyjątkiem 9. Jeśli tylko jeden z kwadratów może przyjąć wartość 2, to musi to być odpowiedź dla tego kwadratu.
Technika pudełkowa
„Technikę skrzynkową” można również zastosować okazjonalnie, gdy geometria niewypełnionych białych komórek na dowolnym etapie rozwiązania nadaje się do tego: poprzez zsumowanie wskazówek dla serii wpisów poziomych (odjęcie wartości dowolnych cyfr już dodany do tych wpisów) i odjąć wskazówki dla w większości nakładających się serii pionowych wpisów, różnica może ujawnić wartość częściowego wpisu, często pojedynczej komórki. Ta technika działa, ponieważ dodawanie jest zarówno asocjacyjne , jak i przemienne .
Powszechną praktyką jest oznaczanie potencjalnych wartości komórek w rogach komórek, dopóki nie zostanie udowodnione, że wszystkie oprócz jednej są niemożliwe; w przypadku szczególnie trudnych łamigłówek, czasami osoby rozwiązujące odnotowują całe zakresy wartości komórek w nadziei na ostateczne znalezienie wystarczających ograniczeń dla tych zakresów od krzyżujących się wpisów, aby móc zawęzić zakresy do pojedynczych wartości. Z powodu ograniczeń przestrzennych niektóre solwery zamiast cyfr używają notacji pozycyjnej, w której potencjalna wartość liczbowa jest reprezentowana przez znak w określonej części komórki, co ułatwia umieszczenie kilku potencjalnych wartości w jednej komórce. Ułatwia to również odróżnienie potencjalnych wartości od wartości rozwiązania.
Niektórzy rozwiązujący używają również papieru milimetrowego , aby wypróbować różne kombinacje cyfr przed zapisaniem ich w siatkach puzzli.
Podobnie jak w przypadku Sudoku, tylko stosunkowo łatwe łamigłówki Kakuro można rozwiązać za pomocą wyżej wymienionych technik. Trudniejsze wymagają użycia różnych rodzajów wzorców łańcuchów, takich samych, jakie pojawiają się w Sudoku (patrz Zadowolenie z ograniczeń oparte na wzorcach i Zagadki logiczne ).
Matematyka Kakuro
Z matematycznego punktu widzenia łamigłówki Kakuro można przedstawić jako problemy programowania liczb całkowitych i są one NP-zupełne . Zobacz także Yato i Seta, 2004.
W łamigłówkach Kakuro można łatwo zidentyfikować dwa rodzaje symetrii matematycznej: ograniczenia minimalne i maksymalne są podwójne, podobnie jak brakujące i wymagane wartości.
Wszystkie kombinacje sum mogą być reprezentowane za pomocą reprezentacji bitmapowej. Ta reprezentacja jest przydatna do określania brakujących i wymaganych wartości za pomocą bitowych operacji logicznych .
Popularność
Puzzle Kakuro pojawiają się w blisko 100 japońskich magazynach i gazetach. Kakuro pozostawało najpopularniejszą łamigłówką logiczną w japońskiej prasie drukowanej do 1992 roku, kiedy Sudoku zajęło pierwsze miejsce. W Wielkiej Brytanii po raz pierwszy pojawili się w The Guardian , a następnie w The Telegraph i Daily Mail .
Zobacz też
- Killer Sudoku , odmiana Sudoku rozwiązywana przy użyciu podobnych technik.
Linki zewnętrzne
- The New Grid on the Block : wprowadzenie gazety The Guardian do Kakuro
- Raport IAENG na temat Kakuro
- Rozwiązuj zagadki Kakuro online