tło
Sudoku to łamigłówka liczbowa, w której, biorąc pod uwagę siatkę podzieloną na pola o rozmiarze , każda liczba od do powinna pojawić się dokładnie raz w każdym rzędzie, kolumnie i pudełku.
W grze w szachy król może przejść do dowolnej (maksymalnie) 8 sąsiednich komórek po kolei. „Przylegający” oznacza tutaj przyleganie w poziomie, w pionie lub po przekątnej.
Trasa króla jest analogią do trasy rycerza; jest to (prawdopodobnie otwarta) ścieżka, która odwiedza każdą komórkę dokładnie raz na danej planszy z ruchami Szachowego Króla.
Zadanie
Rozważ siatkę Sudoku 6 na 6:
654 | 321
123 | 654
----+----
462 | 135
315 | 246
----+----
536 | 412
241 | 563
oraz trasa króla (od 01
do 36
):
01 02 03 | 34 35 36
31 32 33 | 04 05 06
---------+---------
30 23 28 | 27 26 07
22 29 24 | 25 09 08
---------+---------
21 19 16 | 10 14 13
20 17 18 | 15 11 12
Trasa składa się z 36 cyfr 654654564463215641325365231214123321
.
Wzięcie innej trasy króla daje większe liczby; na przykład mogę znaleźć ścieżkę, która zaczyna się od, 65<6>56446556...
która jest zdecydowanie większa od powyższej. Możesz zmienić planszę Sudoku, aby uzyskać jeszcze wyższe liczby:
... | ...
.6. | ...
----+----
..6 | ...
.5. | 6..
----+----
.45 | .6.
6.. | 5..
Ta niekompletna tablica podaje sekwencję początkową, 666655546...
która jest optymalną sekwencją 9 cyfr początkowych.
Twoim zadaniem jest znalezienie największej takiej liczby dla standardowego Sudoku 9 na 9 z polami 3 na 3 , tj
... | ... | ...
... | ... | ...
... | ... | ...
----+-----+----
... | ... | ...
... | ... | ...
... | ... | ...
----+-----+----
... | ... | ...
... | ... | ...
... | ... | ...
Pamiętaj, że to wyzwanie nie jest golfem kodowym ; skupiamy się raczej na znalezieniu rozwiązań niż na napisaniu małego programu, który teoretycznie działa.
Kryterium punktacji i wygranej
Wynik zgłoszenia to 81-cyfrowy numer znaleziony przez Twój program. Zgłoszenie z najwyższym wynikiem wygrywa. Twój program powinien także wypisać planszę Sudoku i trasę króla w czytelnej dla człowieka formie; dołącz je do swojego zgłoszenia.
Twój program może wyświetlać wiele wyników; Twój wynik to ich maksimum.
Twój program nie ma limitu czasu. Jeśli Twój program nadal działa, a następnie znajdzie wyższą liczbę, możesz zaktualizować wynik przesłania, edytując post. Tiebreaker to najwcześniejszy czas na osiągnięcie wyniku, tj. Albo czas wysłania (jeśli nie jest jeszcze edytowany), albo czas edycji, kiedy wynik został zaktualizowany (w przeciwnym razie).
źródło
Odpowiedzi:
Python + Z3 , 999899898789789787876789658767666545355432471632124566352413452143214125313214321, optymalny
Działa za około pół godziny, produkując
Kod
źródło