Niedawno dostałem nową aplikację Sudoku, która produkuje naprawdę trudne Sudoku, której nie można rozwiązać za pomocą standardowych strategii. Musiałem więc nauczyć się kilku nowych. Jedną z tych strategii jest strategia Y-Wing . Jest klasyfikowany w kategorii „Trudne strategie”, ale tak naprawdę nie jest tak trudny.

Przykład

W tej strategii ważne są tylko 4 komórki. Dlatego zignorowałem wszystkie inne komórki na obrazach.

Patrzymy na wszystkich kandydatów do każdej komórki. W poniższym przykładzie mamy komórkę z kandydatami 3 7(co oznacza, że ​​już odrzuciliśmy kandydatów 1 2 4 5 6 8 9, na przykład ponieważ jest 1w tym samym rzędzie, 2w tym samym polu 3x3, ...), komórka z kandydatami 6 7, komórka z kandydatami 3 6i komórka z kandydatami 2 6. Strategia Y-Wing zasugeruje, że 6można usunąć kandydatów z uczciwej komórki, pozostawiając tylko 2kandydata, którego można wypełnić. Znaleźliśmy więc prawidłową liczbę i jesteśmy o krok bliżej w rozwiązaniu pełnego Sudoku.

Dlaczego można 6je usunąć?

Wyjaśnienie

Załóżmy, że 6jest to poprawna liczba dla zwykłej komórki. Teraz jest 6w tej kolumnie, dlatego możemy usunąć 6kandydatów z prawej górnej komórki, pozostawiając tylko jedną 7, którą możemy wypełnić. To samo dzieje się z lewą dolną komórką. Możemy usunąć 6i wypełnić 3. Teraz, gdy spojrzymy na lewą górną komórkę, dostaniemy sprzeczność. Ponieważ teraz jest już 7w tym samym wierszu i 3tej samej kolumnie, więc możemy usunąć 7i 3z kandydatów, nie pozostawiając żadnych kandydatów. Co oczywiście nie jest możliwe. Dlatego liczba 6 nie może być poprawną liczbą dolnej komórki.

Dokładniej: jeśli mamy 4 komórki z kandydatami [A B] [A C] [C D] [B C](w tej kolejności lub obrócone kołowo), a komórki są połączone (tym samym rzędem, tą samą kolumną lub tym samym pudełkiem 3x3) w okręgu (komórka 1 jest połączona z komórką 2, która jest podłączony do komórki 3, która jest połączona z komórką 4, która jest połączona z komórką 1), niż można usunąć Cz [C D]komórki. Istotne jest, że trzy komórki [A B], [A C]i [B C]zawierać tylko dwóch kandydatów każdy. Inaczej komórka [C D], która może zawierać więcej lub mniej ( Dmoże wynosić zero, jeden lub nawet więcej kandydatów).

Zauważ, że wyraźnie powiedziałem, że można je połączyć w dowolny sposób. W następnym przykładzie możesz ponownie zastosować strategię. Ale tym razem 4 komórki nie tworzą prostokąta. Komórki w dół po lewej i po prawej są po prostu połączone, ponieważ znajdują się w tym samym pudełku 3x3. Y-Wing mówi, że możemy usunąć 1kandydata z lewej górnej komórki. Tym razem w tej komórce pozostało jeszcze 2 kandydatów, więc nie znaleźliśmy nowej poprawnej liczby. Niemniej jednak usunięcie 1puszki może otworzyć drzwi do różnych strategii.

Jeśli chcesz uzyskać więcej informacji o strategii lub kilka innych przykładów, odwiedź sudokuwiki.org .

Specyfikacja wyzwań

Otrzymasz 4 listy jako dane wejściowe, reprezentujące kandydatów komórek. Cztery komórki są połączone jak koło (komórka 1 jest połączona z komórką 2, która jest połączona z komórką 3, która jest połączona z komórką 4, która jest połączona z komórką 1). Możesz założyć, że każda lista jest posortowana w porządku rosnącym.

Twoim zadaniem jest usunięcie jednego kandydata (poprzez zastosowanie strategii Y-Wing) i zwrócenie powstałych list kandydatów w tej samej kolejności. Jeśli nie możesz zastosować strategii, po prostu zwróć te same listy kandydatów.

Jeśli istnieją dwa możliwe rozwiązania (możesz usunąć A z komórki B lub usunąć C z komórki D), zwróć tylko jedno rozwiązanie. Nie ma znaczenia który.

Dane wejściowe mogą mieć dowolną natywną listę lub format tablicy. Możesz także użyć listy list lub czegoś podobnego. Możesz otrzymać dane wejściowe za pomocą STDIN, argumentu wiersza poleceń, pytania lub argumentu funkcji i zwrócić dane wyjściowe za pomocą wartości zwracanej lub po prostu drukując do STDOUT.

To jest golf golfowy. Najkrótszy kod (w bajtach) wygrywa.

Przypadki testowe

[3 7] [6 7] [2 6] [3 6]       => [3 7] [6 7] [2] [3 6]   # Example 1
[6 7] [2 6] [3 6] [3 7]       => [6 7] [2] [3 6] [3 7]   # Example 1, different order
[2 6] [3 6] [3 7] [6 7]       => [2] [3 6] [3 7] [6 7]   # Example 1, different order
[3 6] [3 7] [6 7] [2 6]       => [3 6] [3 7] [6 7] [2]   # Example 1, different order
[1 2 8] [1 8] [8 9] [1 9]     => [2 8] [1 8] [8 9] [1 9] # Example 2
[3 8] [4 8] [3 4 8] [3 4]     => [3 8] [4 8] [3 8] [3 4]
[1 3 6 7 8] [3 8] [3 4] [4 8] => [1 3 6 7] [3 8] [3 4] [4 8]
[7 8] [7 8] [4 7] [4 8]       => [7 8] [8] [4 7] [4 8] or [7] [7 8] [4 7] [4 8]
[4 7] [7 8] [4 8] [4]         => [4 7] [7 8] [4 8] []    # Fictional example
[3 7] [2 6] [6 7] [3 6]       => [3 7] [2 6] [6 7] [3 6] # Y-Wing can't be applied here
[4 7] [2 7 8] [4 8] [1 4]     => [4 7] [2 7 8] [4 8] [1 4] # -||-

CJam, 90 bajtów

Ugh, to jest za długie z powodu ograniczenia, że ​​pozostałe 3 komórki powinny mieć tylko 2 kandydatów.

l~_:_(a+2/::&_{,}$2>:&:Y;{:PY&Y{P1<}?~}%:X,3>1${,}$W=_,2>\Y&,1?*{X:_(+2/{~:I=}#)_2$=I-t}&p

Oczekuje danych wejściowych jako listy listy w formacie CJam. Na przykład:

[[2 6] [3 6] [3 7] [6 7]]

daje wynik w postaci listy CJam formatu listy:

[[2] [3 6] [3 7] [6 7]]

Dodam wyjaśnienie, gdy skończę grać w golfa ..

Wypróbuj online tutaj lub wypróbuj cały pakiet testowy tutaj .

Mathematica, 124 110 bajtów

Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])&

Przykłady:

In[1]:= yWing = Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])& ;

In[2]:= yWing[{{3, 7}, {6, 7}, {2, 6}, {3, 6}}]

Out[2]= {{3, 7}, {6, 7}, {2}, {3, 6}}

In[3]:= yWing[{{4, 7}, {7, 8}, {4, 8}, {4}}]

Out[3]= {{4, 7}, {7, 8}, {4, 8}, {}}