/ / Jak analizować grę podobną do masterminda przy użyciu logicznych zależności - algorytm, zbiór, logika

Jak analizować grę typu mastermind przy użyciu logicznych zależności - algorytm, zbiór, logika


OŚWIADCZENIE: NIE szukam rozwiązania dla Mastermind.


Próbuję napisać program, który rozwiąże grę podobną do masterminda, a ja trochę utknąłem. Nie chcę pełnego rozwiązania, tylko pomagam w części, której nie mogę przejść. Oto gra:

Tam są N możliwe kolory znane z góry. Istnieje nieznany zestaw (prawdopodobnie z powtórzeniami) k które są wybrane i utrzymywane w tajemnicy. Celem jest odgadnięcie kolorów (z powtórzeniami) w tajnym zestawie. Pozwolę sobie ponownie podkreślić, że jest to zestaw, więc kolejność nie ma znaczenia, ale powtórzenia są dozwolone. Na przykład

Kolory są a,b,c,d,e,f,g,h (N=8) i nieznany zestaw to {a,c,c} (k=3).

Wykonywane są kolejne domysły, które dają więcej informacji o tajnym zestawie. Każde odgadnięcie musi być zbiorem (dozwolone powtórzenia) k zabarwienie. Odpowiedzią na każde odgadnięcie jest liczba wspólnych kolorów pomiędzy odgadywaniem i nieznanymi powtórzeniami liczenia zestawów. Na przykład

  1. Odgadnąć: a,d,e Wynik: 1

  2. Odgadnąć: b,c,f Wynik: 1

  3. Odgadnąć: a,a,g Wynik: 1

  4. Odgadnąć: a,c,h Wynik: 2

  5. Odgadnąć: b,e,h Wynik: 0

Te domysły są tworzone przez kogoś innego. Moje cele to:

- Określić, kiedy znana jest informacja o określonym kolorze.

- Określić, kiedy nieznany zbiór może zostać logicznie wydedukowany.

Na początku gry żaden kolor nie jest zdecydowanie w zestawie, ani zdecydowanie nie w nieznanym zestawie (zakładając N>1). Po zgadywaniu, które skutkuje 0, wszystkie kolory tego odgadnięcia nie są znane w nieznanym zestawie. Jeśli wynik jest k, wtedy wszystkie kolory tego odgadnięcia są znanebyć w nieznanym zestawie. Mam problem z napisaniem programu, aby dowiedzieć się wszystkich przypadków pomiędzy .Na przykład, nic nie wiadomo na pewno o jednym z kolorów aż do ostatniego domysłu powyżej. Po ostatnim zgadnięciu, zestaw jest znany jako a,c,c. Logika jest następująca:

  • Do 5, b,e,h nie są w nieznanym zestawie
  • 4, a,c są w nieznanym zestawie
  • O 1, d nie znajduje się w nieznanym zestawie
  • O 2, f nie znajduje się w nieznanym zestawie
  • O 3, g nie znajduje się w nieznanym zestawie
  • Dlatego jedynymi kolorami w nieznanym zestawie są a i c.
  • O 3, a nie jest w nieznanym zestawie więcej niż jeden raz.
  • Dlatego nieznany jest zestaw a,c,c.

Mogę pracować w ten sposób w sposób logiczny, ale nie jestem pewien, jak to wszystko zaprogramować, jeśli ktoś mógłby zaproponować zorganizowany sposób, aby to osiągnąć, byłoby świetnie. Wolałbym objaśnienie wysokiego poziomu z pseudokodem, niż pełną implementację w dowolnym języku. Dzięki.

Odpowiedzi:

1 dla odpowiedzi № 1

Proste podejście: Zbuduj całkowitą populację możliwych kombinacji. Następnie, gdy pojawiają się domysły, usuń kombinacje, które nie mogą spełnić wyniku dla bieżącego odgadnięcia. Gdy masz już tylko jedną kombinację, to rozwiązanie, lub wcześniej, gdy nie ma już określonego koloru, to jest (oczywiście) wyeliminowany z możliwego tajnego kodu.


1 dla odpowiedzi nr 2

Możesz zakodować logikę po każdym odgadnięciu w następujący sposób. Weź tablicę długości N, gdzie wejście pozycji i jest +1 jeśli ith kolor jest w zestawie, -1 jeśli ith kolor nie jest w zestawie i 0 jeśli nie wiadomo, czy ith kolor jest w zestawie.

Po każdym odgadnięciu, tworzysz możliwe tablice spełniające wynik. Jeśli zgadnie wynik r, wtedy będzie (k choose r) (lub mniej, jeśli występują powtarzające się kolory) możliwe tablice. Na przykład tablice są (tutaj użyłem + zamiast +1 i - zamiast -1 dla zwięzłości)

  1. (+,0,0,-,-,0,0,0) | (-,0,0,+,-,0,0,0) | (-,0,0,-,+,0,0,0)
  2. (0,+,-,0,0,-,0,0) | (0,-,+,0,0,-,0,0) | (0,-,-,0,0,+,0,0)
  3. (+,0,0,0,0,0,-,0) | (-,0,0,0,0,0,+,0)
  4. (+,0,+,0,0,0,0,-) | (+,0,-,0,0,0,0,+) | (-,0,+,0,0,0,0,+)
  5. (0,-,0,0,-,0,0,-)

Teraz możesz sprawdzić spójność międzyMożliwości w momencie pojawienia się informacji. Po pierwszym przypuszczeniu istnieją 3 możliwości, z których każda jest równie ważna. Po drugim odgadnięciu istnieje 9 możliwości (1 z pierwszych 3 i 1 z drugiej 3) i każda z nich jest ważna. Po trzecim przypuszczeniu istnieje 18 możliwości, z których tylko 9 jest ważnych. Dzieje się tak dlatego, że opcja lewa od 3 wymaga lewej opcji od 1 i odwrotnie. Po czwartym przypuszczeniu istnieje 5 ważnych możliwości. Po piątym przypuszczeniu istnieje tylko jedna ważna możliwość, a mianowicie:

  1. (+,0,0,-,-,0,0,0)
  2. (0,-,+,0,0,-,0,0)
  3. (+,0,0,0,0,0,-,0)
  4. (+,0,+,0,0,0,0,-)
  5. (0,-,0,0,-,0,0,-)

Teraz włączanie / wyłączanie każdego koloru jest znane. Możesz obsługiwać krotności w podobny sposób.


0 dla odpowiedzi № 3

Knuth opisane rozwiązanie. ja wdrożony to.


0 dla odpowiedzi nr 4

Wybrane pozycje: ade = 1 => 3 możliwe 100, 010, 001

Nieznany dla tej linii: bcfgh =? => 5 pozycji = 32 możliwych

połącz je, aby dać 32 * 3 = 96 możliwych odpowiedzi

powtórz dla następnej linii i usuń te, które nie są możliwe dla wszystkich linii

pozostało tylko jedno możliwe