C++: Az n-királynő probléma brute force megoldása

Programozással kapcsolatos cikkek / C, C++ (1408 katt)

A feladat

Az n-királynő probléma a következő: helyezzünk el n db királynőt egy (általánosított) n x n-es sakktáblán úgy, hogy a királynők ne üssék egymást. Ez a sakk szabályai szerint azt jelenti, hogy két királynő nem állhat a tábla azonos során vagy oszlopán, illetve azonos átlón.

A feladat megoldása jelentheti azt, hogy keressünk egy konkrét jó elhelyezést, illetve azt is, hogy keressük meg az összes lehetséges elhelyezést.

Reprezentáció

Az n-királynő problémát többféle módon is lehet reprezentálni.

Az első módszer szerint egy n x n-es kétdimenziós tömböt használunk, ahol a tomb[i, j] helyen található 1 érték jelzi azt, hogy az i. sor j. oszlopában van királynő, a 0 pedig azt, hogy nincs. Ebben az esetben ha minden lehetséges állást meg szeretnénk vizsgálni, akkor nagyon nagy számot kapnánk. A 8 királynő esetén például ( 64 8 ) = 4 426 165 368 ( 64 alatt a 8 ) esetet kellene végignézni.

Ha felhasználjuk azt a tényt, hogy két királynő sosem állhat egy oszlopban, akkor egy egydimenziós, n elemű tömb is megfelel, amelyben az egyes számok azt jelentik, hogy a tömb indexének megfelelő oszlop hányadik sorában áll egy királynő. Ha minden esetet meg szeretnénk vizsgálni a 8 királynő esetén, akkor már csak 8^8 = 16 777 216 eset jönne szóba. Ez az ábrázolási mód a visszalépéses keresés esetén használható, mely esetben az algoritmus jelentősen csökkenti a megvizsgált állások számát.

A harmadik lehetséges módszer esetében azt a tényt is figyelembe vesszük, hogy két királynő sem azonos oszlopban, sem azonos sorban nem állhat. Ekkor egy egydimenziós, n elemű tömböt használunk, amelyben az egyes számok az előző esethez hasonlóan azt jelentik, hogy a tömb indexének megfelelő oszlop hányadik sorában áll egy királynő, viszont a tömb mindig az 1..n számok egy permutációját tartalmazza. Ha az összes esetet meg szeretnénk vizsgálni, amely a mai számítógépek esetén kis n esetén elfogadható időn belül megvalósítható, akkor ezt az ábrázolást célszerű használni. A 8 királynő esetén a megvizsgált állások száma így már csak 8! = 40 320 darab lesz.

A helyes megoldások száma

A program futtatása során az n különböző értékeire a következő megoldás darabszámokat kaptam:


Királynők száma (n) Megoldások száma
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680



Az elkészített program

A feladat megoldására a Microsoft Visual Studio 2015-ös verzióját és a C++ nyelvet használtam. A program az összes lehetséges permutáció vizsgálatát végzi el. Ebben az esetben szükség van a szóba jövő permutációk előállítására. A C++ nyelv használata esetén erre létezik kész megoldás (algorithm, next_permutation), amit fel is használtam a programban.

A program az indítása után bekéri a felhasználótól az n értékét, amely a képernyőre kiírt határok közé eshet. Ezután az adott programban megvalósított módszerrel megkeresi a feladat összes lehetséges megoldását, és ezeket kiírja a képernyőre.

A kiírás formátuma:

1 3 5 2 4

Ez azt jelenti, hogy az első oszlop első sorában, majd a második oszlop harmadik sorában, az ötödik oszlop ötödik sorában stb. áll egy-egy királynő.

Miután befejeződött a keresés, a program megkérdezi a felhasználót, hogy akar-e újabb keresést végezni. Ha i-vel válaszolunk, akkor egy újabb n értéket adhatunk meg, egyébként a program kilép.

A program forráskódja

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int MAXN = 11;

typedef int Tabla[MAXN];

void Koszonto()
{
cout << "Az N királynő probléma megoldása az összes eset vizsgálatával"
<< endl;
cout << "-------------------------------------------------------------"
<< endl;
cout << "Készítette: Török Viktor" << endl;
cout << endl;
}

int MeretBekerese()
{
int n = 0;

do
{
cout << "Kérem, adja meg n értékét (1 - " << (MAXN - 1) << "): ";
cin >> n;

if (cin.fail())
{
cin.clear();
cin.ignore(numeric_limits<int>::max(), '\n');
}
} while (n < 1 || n >= MAXN);

return n;
}

bool KovetkezoEset()
{
string kov;
cout << "Következő eset (i / n): ";
cin >> kov;

return kov == "i" || kov == "I";
}

void TablaInicializalasa(Tabla tabla, int n)
{
for (int i = 0; i < n; i++)
{
tabla[ i ] = i;
}
}

void TablaKiirasa(Tabla tabla, int n)
{
for (int i = 0; i < n; i++)
{
cout << (tabla[ i ] + 1) << " ";
}

cout << endl;
}

bool Megoldas(Tabla tabla, int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if ((j - i) == abs(tabla[j] - tabla[ i ]))
{
return false;
}
}
}

return true;
}

void MegoldasokKeresese(Tabla tabla, int n)
{
int darab = 0;

cout << "A megoldások:" << endl;

do
{
if (Megoldas(tabla, n))
{
TablaKiirasa(tabla, n);
darab++;
}
} while (next_permutation(tabla, tabla + n));

cout << "---------------------------" << endl;
cout << "A megoldások száma " << n << " királynő esetén: " << darab
<< endl;
}

int main()
{
setlocale(LC_ALL, "");

Tabla tabla;

Koszonto();

do
{
int n = MeretBekerese();

TablaInicializalasa(tabla, n);
MegoldasokKeresese(tabla, n);
} while (KovetkezoEset());

return 0;
}


Előző oldal Kapitány