Rozwiązywanie Kakuro puzzle

Question

Oto dobry do refleksji na temat:

http://en.wikipedia.org/wiki/Kakuro

Ja próbuje dokonać solver dla tej gry. Dokumentacja jest skończona (czytanie pliku początkowego ze zmienną liczbą kolumn i wierszy) Zakłada się, że plik wejściowy jest zgodny z regułami gry, więc gra jest zawsze możliwa do rozwiązania. Poświęć trochę czasu na przeczytanie zasad gry:

I Wcześniej pod opieką struktury danych, które myślę, że będzie pasować najlepiej:

struct aSquare { int verticalSum; int horizontalSum; int value; } 

i złożył «tablicę» tych dynamicznie pracować na zrobiłem to tak, że czarne kwadraty mają wartość -1. białe kwadraty (rzeczywiste kwadraty rozwiązania) inicjalizują się w punkcie 0. Można również łatwo uzyskać położenie każdej struktury aSquare z tablicy, bez potrzeby tworzenia dla niej dodatkowych pól struktury.

Teraz algorytm ... W jaki sposób na świecie rozjemcę wszystkie te sumy i znajdę ogólny sposób, który rozwiąże wszystkie rodzaje sieci. Walczyłem z tym przez całe popołudnie bezskutecznie.

Pomoc jest doceniana, baw się dobrze!

* EDYCJA: Właśnie zdałem sobie sprawę, że opublikowany link zawiera kilka wskazówek dotyczących technik rozwiązywania. Nadal będę to sprawdzać, aby zobaczyć, co ludzie wymyślą.

Answer 1

Prosty brute-force na Sudoku solver trwa milisekundy biegać, więc nie trzeba się przejmować wykonania żadnych specjalnych taktyk. Myślę, że w przypadku Kakuro to będzie to samo. Prosty algorytm:

def solve(kakuro): 
    if kakuro has no empty fields: 
     print kakuro 
     stop. 
    else: 
     position = pick a position 
     values = [calculate possible legal values for that field] 
     for value in values: 
      kakuro[position] = value 
      solve(kakuro) 
     kakuro[position] = None # unset after trying all possibilities 

Ten algorytm może działać lepiej, jeśli znajdziesz najlepszą kolejność pól do wypełnienia. Spróbuj wybrać pola, które będą najbardziej ograniczone (jak w: nie ma wielu wartości, które są legalne).

W każdym razie najprawdopodobniej będzie to najprostsze do wykonania, więc spróbuj i poszukaj bardziej wyrafinowanych rozwiązań tylko wtedy, gdy ten nie zadziała. (W rzeczywistości jest to jeden z najprostszych solverów programistycznych, a prawdziwe rozwiązania CP są oczywiście bardziej skomplikowane).

Answer 2

Jest to prosta algebra liniowa, należy użyć technik manipulacji wektor/macierz do rozwiązania.

[edit - odpowiadając na komentarze]

a + b + 0 + d + 0 = n1 
0 + b + c + 0 + e = n2 
a + 0 + c + 0 + 0 = n3 
a + b + c + 0 + e = n4 
a + 0 + c + d + 0 = n5 

powyżej jest konwertowany do matrycy, a przez dodawanie i odejmowanie wielokrotności wierszy, możesz skończyć z:

a 0 0 0 0 na 
0 b 0 0 0 nb 
0 0 c 0 0 nc 
0 0 0 d 0 nd 
0 0 0 0 e ne 

Brak kombinatoryki, wszystkie pozostają liczbami całkowitymi.

Answer 3

Jeśli Twoim zainteresowaniem jest ostatecznie tworzenie oprogramowania do tych gier, ale nie dostaniesz się do szczegółów algorytmu, polecam użycie silnika do programowania wiązań (CP). CP to deklaratywny paradygmat programowania, który bardzo dobrze nadaje się do tego rodzaju problemów. Dostępnych jest kilka komercyjnych i otwartych źródeł CP.

http://en.wikipedia.org/wiki/Constraint_programming

Answer 4

Przypuszczam, że Linear Programming mogą być łatwo wykorzystane do rozwiązania tego rodzaju gry .. to jest to problem, dla których całkowita dokładne rozwiązania nie istnieją .. (metoda podziału i ograniczeń? cięcia-plane?)

W każdym przypadku przy użyciu tabeli z najbardziej pewnych kombinacjach będzie przydatna na pewno (np http://www.enigmoteka.com/Kakuro%20Cheatsheet.pdf)

Answer 5

znalazłem kilka ciekawych sztuczek bit manipulacji, które przyspieszają rozwiązywanie Kakuro. Możesz pobrać źródło here.

Answer 6

Jeśli chodzi o ograniczanie Programowanie: Oto kilka różnych sposobów rozwiązania łamigłówki Kakuro z programowaniem wiązań (wszystkie przy użyciu tej samej podstawowej zasady). Instancja problemu została naprawiona w programie.

• lub Google-tools/Python: http://www.hakank.org/google_or_tools/kakuro.py
• Comet: http://www.hakank.org/comet/kakuro.co
• MiniZinc: http://www.hakank.org/minizinc/kakuro.mzn
• SICStus: http://www.hakank.org/sicstus/kakuro.pl
• Eclipse: http://www.hakank.org/eclipse/kakuro.ecl
• Gecode: http://www.hakank.org/gecode/kakuro.cpp
• Google lub- narzędzia/C#: http://hakank.org/google_or_tools/kakuro.cs
• Odpowiedź została ustawiona Programowanie: http://hakank.org/asp/kakuro.lp

Edycja: Dodano Google lub-tools/C# i odpowiedzi zestaw programowania.