8 Queens Problem C ++

C ++ kan brukes til å løse veldig komplekse, men interessante problemer programmatisk. Et slikt avgjørende problem i C ++ er N-Queens 'problem, der "N" representerer det totale antallet dronninger på sjakkbrettet. Nå lurer du kanskje på hva dette problemet faktisk er og hvordan du kan løse det med C++. Du vil kunne finne ut svarene på disse spørsmålene etter å ha gått gjennom denne artikkelen.

Hva er 8 Queens -problemet i C++?

N-Queens 'eller 8 Queens' problem refererer til situasjonen du vil plassere det gitte antallet dronninger på en sjakkbrett på en måte som ingen dronning kan angripes av en annen vertikalt, horisontalt eller diagonalt, jeg.e., Alle dronningene skal plasseres så intelligent at ingen av dem kan angripes av den andre på noen måte.

Hvordan løse 8 Queens -problemet i C ++ i Ubuntu 20.04?

I dette segmentet vil vi dele med deg prosedyren for å løse de 8 dronningens problem i C++. For å oppnå dette målet har vi designet en C ++ -kode vist på bildet nedenfor. Før vi fortsetter med å forklare denne koden, vil vi imidlertid dele med deg at vi har brutt ned denne koden til små utdrag for din enkle forståelse. Vi har omtrent delt dette C ++ -programmet i en funksjon for å skrive ut alle de forskjellige tilstandene i sjakkbrettet som tilfredsstiller løsningen av 8 Queens 'problem, en funksjon for å sjekke om en bestemt stilling er trygg for å plassere dronningen eller ikke, en funksjon for Løsning av 8 Queens 'problem ved hjelp av backtracking -algoritmen, og til slutt, hoveddriverfunksjonen. Vi vil diskutere alle disse utdragene en etter en.

I det første utdraget av koden vår, etter å ha inkludert biblioteket og navneområdet, har vi definert et sjakkbrett med størrelse 10 x 10 i form av en 2D -matrise. Det betyr at programmet vårt vil være i stand til å ta 10 dronninger 'maksimalt for å løse N-Queens' problem i C++. I denne artikkelen er vi imidlertid hovedsakelig opptatt av 8 Queens 'problem. Etter å ha definert sjakkbrettet, har vi vår "printboard" -funksjon som tar et heltall "n" som inngang som refererer til antall dronninger, i.e., 8 I dette tilfellet. Innenfor denne funksjonen har vi en nestet "for" -sløyfe for bare å skrive ut sjakkbrettet på terminalen hver gang denne funksjonen kalles. Deretter har vi noen "cout" uttalelser for å skrive ut tilstrekkelige mellomrom mellom de forskjellige tilstandene i det løse sjakkbrettet.

I det andre utdraget av vår C ++ -kode har vi "Issafe" -funksjonen som er der for å sjekke om det vil være trygt å plassere en dronning i en bestemt posisjon eller ikke. Med "trygt" mener vi at ingen annen dronning kan angripe en bestemt dronning vertikalt, horisontalt eller diagonalt. Deretter har vi tre uavhengige “for” -løkker innen denne funksjonen som er der for å bekrefte alle de tre forholdene hver for seg. Hvis noen av disse forholdene blir sanne, vil "issafe" -funksjonen returnere "falsk" fordi det i disse tilfellene alltid vil være en sjanse for angrep, på grunn av at vi ikke vil kunne plassere en dronning i den spesielle posisjonen. Imidlertid, hvis alle disse forholdene blir falske, jeg.e., Det er ingen sjanse for angrep i den posisjonen vertikalt, horisontalt eller diagonalt, først da vil "issafe" -funksjonen returnere "sant" i.e., Det vil være trygt å plassere en dronning i den aktuelle posisjonen.

I det tredje utdraget av vår C ++ -kode har vi "løsning" -funksjonen som vil utvikle løsningen av N-Queens 'problem ved å bruke backtracking-algoritmen. Innenfor denne funksjonen brukes den første "hvis" -uttalelsen for å sjekke om dronningnummeret er lik det totale antallet dronninger eller ikke. Hvis denne uttalelsen evaluerer å være sann, vil "printboard" -funksjonen øyeblikkelig bli kalt. Ellers vil et boolsk variabelt "resultat" bli definert hvis opprinnelige tilstand holdes "falsk". Deretter har vi en annen "for" -sløyfe som vi iterativt kaller "issafe" -funksjonen for hver av dronningene for å finne ut om den gitte posisjonen er trygg for å plassere den eller ikke. Innenfor denne tilstanden har vi brukt rekursjon for å utføre backtracking for å plassere dronningene i de tryggeste stillingene, slik at de ikke kan bli angrepet av noen annen dronning. Her vil “1” representere at en dronning er plassert i en bestemt posisjon, mens “0” vil representere alle de tomme posisjonene til sjakkbrettet. Til slutt har vi returnert "resultat" -variabelen for å varsle om løsningen på det gitte antallet dronninger er mulig eller ikke.

I det siste utdraget av C ++ -koden vår har vi hoveddriverfunksjonen. Årsaken til å bruke de to første utsagnene i vår "Main ()" -funksjon er ytelsesoptimalisering fordi for et større antall dronninger kan programmet ditt utføre urimelig saktere. Imidlertid kan du hoppe over disse hvis du ønsker det. Deretter har vi definert et heltall "n" som tilsvarer antall dronninger. Etter det har vi vist en melding på terminalen for å be brukeren om å legge inn antall dronninger som han/hun ønsker å løse N-Queens 'problem. Deretter har vi ganske enkelt skaffet dette som innspill fra brukeren. Etter det har vi en nestet "for" -sløyfe der vi har kalt "Chessboard" -funksjonen. Deretter har vi kalt "løsning" -funksjonen og lagret utdataene i "Resultat" -variabelen. Hvis verdien av "resultatet" -variabelen vil være "falsk", vil det bety at det ikke eksisterer noen løsning for det gitte antallet dronninger. Endelig har vi "Return 0" -erklæringen for innpakning av koden vår.

For å kompilere denne koden har vi brukt følgende kommando:

$ G ++ 8QUEENS.CPP -o 8queens

For å kjøre denne koden har vi brukt kommandoen vedlagt nedenfor:

$ ./8queens

Vi ble først bedt om å gå inn i antall dronninger som vist i følgende bilde:

Vi har skrevet inn "8" for vår spesielle sak, som vist på bildet nedenfor:

Så snart du gir antall dronninger, vises alle mulige løsninger på 8 Queens 'problem på terminalen som vist i følgende bilde:

For å teste denne koden for den andre saken, jeg.e., Løsningen eksisterer ikke, vi har gitt "3" som antall dronninger. Dette vises på bildet nedenfor:

Vi forstår at for et 3 x 3 sjakkbrett eksisterer det ingen løsning; Derfor mottok vi følgende utdata:

Konklusjon

Denne artikkelen handlet om 8 Queens 'problem i C ++ i Ubuntu 20.04. Vi forklarte deg kort om dette problemet og alle forholdene som må tilfredsstilles for å løse dette problemet. Etter det delte vi deg et fullverdig C ++ -program som vil løse dette problemet for deg for 8 Queens eller på Max 10 Queens. Videre testet vi også denne koden for en sak der løsningen på dette problemet er umulig. Forhåpentligvis, etter å ha lest gjennom denne guiden, vil du få en god forståelse av de berømte 8 Queens 'problem i C++.