Zaimplementuj najkrótszy solver Sudoku za pomocą zgadywania. Ponieważ otrzymałem kilka próśb, dodałem to jako alternatywne pytanie dla osób pragnących wdrożyć solute sudoku z brutalną siłą.
Sudoku Puzzle:
| 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 3 | 1 |
B| 6 | | 5
C| 5 | | 9 8 3
-+-----------------------
D| 8 | 6 | 3 2
E| | 5 |
F| 9 3 | 8 | 6
-+-----------------------
G| 7 1 4 | | 9
H| 2 | | 8
I| | 4 | 3
Odpowiedź:
| 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7
Zasady:
- Załóżmy, że wszystkie labirynty można rozwiązać tylko za pomocą logiki.
- Wszystkie dane wejściowe będą miały 81 znaków. Brakujące znaki będą wynosić 0.
- Wyjście rozwiązania jako pojedynczy ciąg.
- „Siatka” może być przechowywana wewnętrznie, jak chcesz.
- Rozwiązanie musi zawierać rozwiązanie zgadywania brutalnej siły.
- Rozwiązania powinny zostać rozwiązane w rozsądnym terminie.
Przykład I / O:
>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
code-golf
game
puzzle-solver
sudoku
snmcdonald
źródło
źródło
Odpowiedzi:
k (72 bajty)
Podziękowania należą się Arthurowi Whitneyowi, twórcy języka K.
źródło
Python, 188 bajtów
To jest kolejna skrócona wersja mojego zwycięskiego zgłoszenia do CodeSprint Sudoku , zmodyfikowanego do wprowadzania z wiersza poleceń zamiast standardowego wejścia (zgodnie z OP):
Jeśli używasz języka Python 2,
'%d'%5**18
możesz go zastąpić,`5**18`
aby zaoszczędzić 3 bajty.Aby przyspieszyć działanie, możesz zastąpić
'%d'%5**18
dowolną permutacją'123456789'
za cenę 1 bajtu.Jeśli chcesz, aby zaakceptować wejście na stdin zamiast można zastąpić
import sys;f(sys.argv[1])
zf(raw_input())
, obniżając ją do 177 bajtów .EDYCJA: Oto link do bardziej szczegółowego przewodnika.
źródło
Python, 197 znaków
źródło
Odpowiedź w D:
Z przykładowym wejściem pobiera .033s na moim Phenom II X6 1090T po kompilacji
dmd -w
(tj. Bez optymalizacji), i zajmuje .011s po kompilacjidmd -w -O -inline -release
(tj. Z optymalizacjami).źródło
J, 103
przewidywany czas pracy: O (miliard miliardów lat)
źródło
Perl, 120 bajtów
Och, pamiętam grę w golfa w 2008 roku ... I tak naprawdę przestał działać w perlu 5.12, ponieważ usunięto wtedy ukryte ustawienie @_ przez podział. Więc wypróbuj to tylko na wystarczająco starym perlu.
Uruchom z wejściem na STDIN:
sudoku.pl
:źródło
Perl, 235 znaków
To jest wersja gry w golfa, którą zamieściłem wiele lat temu na liście dyskusyjnej Fun With Perl : regexp rozwiązujący sudoku.
Zasadniczo porządkuje dane wejściowe w 81 liniach, z których każda zawiera wszystkie liczby, które mogą wystąpić w odpowiednim kwadracie. Następnie konstruuje wyrażenie regularne w celu dopasowania jednej liczby z każdej linii, wykorzystując odwołania wsteczne i negatywne twierdzenia dotyczące przyszłości, aby odrzucić rozwiązania naruszające ograniczenia wiersza, kolumny lub regionu. Następnie dopasowuje ciąg do wyrażenia regularnego, pozwalając silnikowi wyrażeń regularnych Perla wykonać ciężką pracę próbną i cofanie się.
O dziwo, możliwe jest utworzenie jednego wyrażenia regularnego, który będzie działał dla dowolnego wejścia, tak jak robi to mój oryginalny program. Niestety jest dość powolny, więc oparłem tutaj kod do gry w golfa na wersji hardcoded-givens ( znalezionej później w wątku FWP ), która poprawia wyrażenie regularne, aby odrzucić wcześniej wszelkie rozwiązania, o których wie, że później naruszą ograniczenie. To sprawia, że jest dość szybki dla łatwych do umiarkowanych poziomów sudokus, chociaż szczególnie trudne mogą jeszcze zająć dość dużo czasu.
Uruchom kod za pomocą,
perl -M5.010
aby włączyć funkcję Perl 5.10+say
. Dane wejściowe należy podać na standardowym wejściu, a rozwiązanie zostanie wydrukowane na standardowym wyjściu; przykład:źródło
1-liniowy skrypt do kawy
solve = (s, c = 0) -> if c is 81 then s else if s[x = c/9|0][y = c%9] isnt 0 then solve s, c+1 else (([1..9].filter (g) -> ![0...9].some (i) -> g in [s[x][i], s[i][y], s[3*(x/3|0) + i/3|0][3*(y/3|0) + i%3]]).some (g) -> s[x][y] = g; solve s, c+1) or s[x][y] = 0
Oto większa wersja z przykładowym użyciem :
źródło
solve
, usuwając wiele białych znaków (wiem, że jest to znaczące, ale w wielu miejscach można go usunąć), używając symboli zamiast słów (jak!=
zamiastisnt
), używając wcięcia zamiastthen
słowa kluczowego, zastępując[0...9]
je[0..8]
.Clojure - 480 bajtów
Rozmiar eksplodował, ale przynajmniej to ładna liczba. Myślę, że można by to znacznie poprawić, używając tylko wektora 1D. W każdym razie przypadek testowy na moim laptopie zajmuje niecałe cztery sekundy. Pomyślałem, że dobrze byłoby zdefiniować funkcję, ponieważ jest to w końcu język funkcjonalny.
Przykłady:
Nieco golfowa (i ładniejsza) wersja:
źródło
PowerShell ,
244242218215 bajtówWypróbuj online!
Skrypt znajduje wszystkie rozwiązania dla sudoku.
Rozwinięty:
Przypadki testowe:
źródło
D (322 znaki)
Dla każdego nierozwiązanego kwadratu buduje tablicę dostępnych opcji, a następnie zapętla nad nim.
z białymi znakami:
źródło
Perl (195 znaków)
Całe uznanie należy do twórcy tutaj , a wyjaśnienie można również tam znaleźć.
źródło
J, 94 bajty
Działa dokładnie tak samo, jak wersja K, a mianowicie z BFS (więc wyświetli wszystkie rozwiązania). Drukuje spacje między cyframi wyjściowymi, ale robi to również program K. Nie liczę „s =:”, ponieważ jest to po prostu nazwa funkcji (tak jak nie liczyłbym nazwy pliku w innym języku).
źródło