8 Problem Queens C ++

C ++ może być używany do programowego rozwiązywania bardzo złożonych, ale interesujących problemów. Jednym z takich kluczowych problemów w C ++ jest problem N-Queens, w którym „N” reprezentuje całkowitą liczbę królowych na szachownice. Teraz możesz zastanawiać się, jaki jest ten problem i jak możesz go rozwiązać za pomocą C++. Po przejrzeniu tego artykułu będziesz mógł znaleźć odpowiedzi na te pytania.

Jaki jest problem 8 królowych w C++?

Problem N-Queens lub 8 Queens odnosi się do sytuacji, w której chcesz umieścić podaną liczbę królowych na szachownicy w sposób, aby żadna królowa nie może zostać zaatakowana przez inny pionowo, poziomo lub diagonalnie, i ja.mi., Wszystkie królowe powinny być ustawione tak inteligentnie, że żaden z nich nie może zostać zaatakowany przez drugiego w żaden sposób.

Jak rozwiązać problem 8 królowych w C ++ w Ubuntu 20.04?

W tym segmencie podzielimy się z Tobą procedurą rozwiązania problemu 8 królowych w C++. Aby osiągnąć ten cel, zaprojektowaliśmy kod C ++ pokazany na poniższym obrazku. Jednak zanim przejdziemy do wyjaśnienia tego kodu, chcielibyśmy podzielić się z Tobą, że podzieliliśmy ten kod na małe fragmenty, aby uzyskać łatwe zrozumienie. Z grubsza podzieliliśmy ten program C ++ na funkcję drukowania wszystkich różnych stanów szachownicy, które spełniają rozwiązanie problemu 8 królowych, funkcję sprawdzania, czy dana pozycja jest bezpieczna do umieszczenia królowej, czy nie, funkcję dla Rozwiązywanie problemu 8 Queens za pomocą algorytmu wycofania, a na koniec główną funkcję sterownika. Będziemy omawiać wszystkie te fragmenty jeden po drugim.

W pierwszym fragmencie naszego kodu, po uwzględnieniu biblioteki i przestrzeni nazw, zdefiniowaliśmy szachownicę o rozmiarze 10 x 10 w postaci tablicy 2D. Oznacza to, że nasz program będzie w stanie wziąć 10 królowych „maksymalnie do rozwiązania problemu N-Queens” w C++. Jednak w tym artykule zajmujemy się głównie problemem 8 Queens. Po zdefiniowaniu szachownicy mamy naszą funkcję „printboard”, która przyjmuje liczbę całkowitą „N” jako wejście, które odnosi się do liczby królowych, i.mi., 8 W tym konkretnym przypadku. W ramach tej funkcji mamy zagnieżdżoną pętlę „dla”, aby po prostu wydrukować szachownicę na terminalu za każdym razem, gdy wywołuje to funkcja. Następnie mamy kilka „cout” do drukowania odpowiednich przestrzeni między różnymi stanami rozwiązanej szachownicy.

W drugim fragmencie naszego kodu C ++ mamy funkcję „Issafe”, która ma sprawdzić, czy bezpiecznie będzie umieścić królową na określonej pozycji, czy nie. Przez „bezpieczne” rozumiemy, że żadna inna królowa nie może zaatakować konkretnej królowej pionowo, poziomo lub po przekątnej. Następnie mamy trzy niezależne pętle „dla” w tej funkcji, które są w celu zweryfikowania wszystkich trzech warunków osobno. Jeśli którykolwiek z tych warunków stanie się prawdziwy, wówczas funkcja „issAfe” zwróci „fałsz”, ponieważ w tych przypadkach zawsze będzie szansa na atak, z czego nie będziemy w stanie umieścić królowej na konkretnej pozycji. Jeśli jednak wszystkie te warunki staną się fałszywe, ja.mi., Nie ma szans na atak w tej pozycji pionowo, poziomo lub po przekątnej, tylko wtedy funkcja „issAfe” zwróci „true” i.mi., Będzie bezpiecznie umieścić królową na konkretnej pozycji.

W trzecim fragmencie naszego kodu C ++ mamy funkcję „rozwiązania”, która opracuje rozwiązanie problemu N-Queens za pomocą algorytmu wycofania. W ramach tej funkcji pierwsza instrukcja „jeśli” jest używana do sprawdzenia, czy liczba królowej jest równa całkowitej liczbie królowych, czy nie. Jeśli to oświadczenie oceni, że jest prawdziwe, wówczas funkcja „printu” zostanie natychmiast wywołana. W przeciwnym razie zostanie zdefiniowany zmienna logiczna „wynik”, którego stan początkowy jest „fałszywy”. Następnie mamy kolejną pętlę „dla”, w której iteracyjnie nazywamy funkcją „issAfe” dla każdego z królowych, aby dowiedzieć się, czy dana pozycja jest bezpieczna do jej umieszczenia, czy nie. W tym stanie użyliśmy rekurencji do wykonania wycofania się do umieszczenia królowych na najbezpieczniejszych pozycjach, aby nie mogły zostać zaatakowane przez żadną inną królową. Tutaj „1” będzie reprezentować, że królowa jest umieszczona w określonej pozycji, podczas gdy „0” będzie reprezentować wszystkie puste pozycje szachowni. Na koniec zwróciliśmy zmienną „wynika”, aby powiadomić, czy rozwiązanie podanej liczby królowych jest możliwe, czy nie.

W ostatnim fragmencie naszego kodu C ++ mamy główną funkcję sterownika. Przyczyną korzystania z dwóch pierwszych instrukcji w ramach naszej funkcji „Main ()” jest optymalizacja wydajności, ponieważ dla większej liczby królowych program może wykonać nieuzasadnioną wolniej. Jednak możesz je pominąć, jeśli chcesz. Następnie zdefiniowaliśmy liczbę całkowitą „N”, która odpowiada liczbie królowych. Następnie wyświetliśmy wiadomość na terminalu, aby skłonić użytkownika do wprowadzenia liczby królowych, dla których chce rozwiązać problem N-Queens. Następnie po prostu nabyliśmy to jako dane wejściowe od użytkownika. Następnie mamy zagnieżdżoną pętlę „dla”, w której nazywaliśmy funkcją „szachowni”. Następnie nazwaliśmy funkcję „rozwiązania” i zapisaliśmy jej wyjście w zmiennej „wyniku”. Jeśli wartość zmiennej „wyniku” będzie „fałszywa”, będzie to oznaczać, że nie ma rozwiązania dla podanej liczby królowych. W końcu mamy instrukcję „Return 0” do podsumowania naszego kodu.

Aby skompilować ten kod, użyliśmy następującego polecenia:

$ g ++ 8queens.CPP -O 8Queens

Aby uruchomić ten kod, użyliśmy poniższego polecenia:

$ ./8queens

Najpierw poproszono nas o wprowadzenie liczby królowych, jak pokazano na poniższym obrazku:

Wprowadziliśmy „8” dla naszego konkretnego przypadku, jak pokazano na poniższym obrazku:

Jak tylko podasz liczbę królowych, wszystkie możliwe rozwiązania problemu 8 królowych pojawią się na terminalu, jak pokazano na poniższym obrazku:

Aby przetestować ten kod w drugiej sprawie, ja.mi., Rozwiązanie nie istnieje, dostarczyliśmy „3” jako liczbę królowych. Jest to pokazane na poniższym obrazku:

Rozumiemy, że w przypadku szachownicy 3 x 3 nie ma rozwiązania; Dlatego otrzymaliśmy następujące dane wyjściowe:

Wniosek

Ten artykuł dotyczył problemu 8 Queens w C ++ w Ubuntu 20.04. Wyjaśniliśmy ci krótko o tym problemie i wszystkich warunkach, które muszą być spełnione w celu rozwiązania tego problemu. Następnie udostępniliśmy Ci pełnoprawny program C ++, który rozwiąże ten problem dla 8 królowych lub przy maksymalnych 10 królowych. Ponadto przetestowaliśmy ten kod pod kątem przypadku, w którym rozwiązanie tego problemu jest niemożliwe. Mamy nadzieję, że po przeczytaniu tego przewodnika dobrze zrozumiesz problem słynnego 8 królowych w C++.