Linktár

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

Programozással kapcsolatos cikkek / C, C++ (1650 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;
}