Kto pomoget?

[CyberJoe]

Narod kto znaet zadachu o 8 korolev v shaxmatax?
------------------
dlja tex kto ne znaet
Nado rasspologit 8 Koroliv na doske shaxmatnoj tak chtobi ni odna druguju ne bila
------------------
Esli kto moget podskazat algoritm pogaluista pomogite.
A esli u kogo on est napisannij na C++ to prishlite
Zaranie spasibo

[MuZe]

ah.. ja ete znaju

palaji tak
E1,A2,H3,f4,C5,G6,B7,D8

[Aram Hambardzumyan]

посмотри в книге вирта 'алгоритмы+структуры данных=программы', там на паскале, но думаю сойдет. а еще я ее на прологе писал, жаль, не сохранилась а то бы попугал

[Eddi]

Originally posted by MuZe:
ah.. ja ete znaju

palaji tak
E1,A2,H3,f4,C5,G6,B7,D8

A posle etogo mogesh' ciklicheski menyat' poloski doski both vertically and horizontally i poluchish' vse vozmognye varianty

A algorithm ochen' prostoj, prosto raspolagaesh' drug za drugom i obychno na 8-om shage mesta ne budet, pojdesh' nazad do xoda kogda u tebya byl vybor, vyberesh' chto-nibud' drugoe i tak dalee. Drugimi slovami - brute force

[petar]

BAYC ET XNDIRI MEJ KAROL CHI KARALEVA A

[BlackMoon]

postav pervuu korolevu v verkhnem levom uglu
sleduushuu postav tochno tak kak esli bi ti
sigral konem v pravo i t.d. tak ti postavish 4
korolevi

potom 5-uu postvishish ot verkhnei levoi opiat
po zakonu khoda konia no uje vnis, i takje ostalnie
4 korolevi

naskolko ia snau eto edinstvenni algorithm

[Eddi]

2 BlackMoon.

Eto skoree ne algoritm, a odno chastnoe reshenie (dlya sluchaya 8x8). Kotoroe vyshe uge bylo ukazano by MuZe. (i esli razlichno to kak ya uge opyat' taki skazal ciklicheskoj perestanovkoj vsex stolbcov i strok mogno poluchit' vse resheniya iz odnogo dannogo)

[CyberJoe]

Originally posted by Eddi:
Ja uznal eta zadacha imeet 92 reshenija!!!

[Eddi]

http://users.net1plus.com/brianl/8queens.htm - this has a java program using recursive algorithm.

I was wrong before stating that you'll get all the solutions from one. There are 12 different solutions (other 80 come from rotations and reflections).

http://mathworld.wolfram.com/QueensProblem.html - also this link gives you the formula to calculate the number of placings for nxn board and k queens.

Have fun

[Artsrun Ohanyan]

Nerkayatcnum em xndri lutsman im tsragir@, vor@ inchpes tesnum eq bavakanin kar& e yev ashxatum e shat arag...
Arajarkeq dzer@...

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void main()
{
	vector< unsigned int > Pattern( 8 );
	for ( unsigned int i = 0; i <= 7; i++ ) 
		Pattern[ i ] = i + 1;

	unsigned int uiCount = 0;
	vector< unsigned int >::iterator start = Pattern.begin(), end = Pattern.end();
	while ( next_permutation( start, end ) )
	{
		bool bFound = true;
		for ( unsigned int i = 0; i <= 7 && bFound; i++ )
			for ( unsigned int j = i + 1; j <= 7 && bFound; j++ )
				bFound = ( abs( Pattern[ i ] - Pattern[ j ] ) != abs( i - j ) );
		if ( bFound )
		{
			uiCount++;
			ostream_iterator< unsigned int > outIt( cout, &quot; &quot; );
			copy( start, end, outIt );
			cout << endl;
		}
	}
	cout << endl << uiCount << &quot; solutions.&quot; << endl;
}

[CyberJoe]

Spasibo!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

[Amph]

Плохой алгоритм.... Идёт тупой перебор, а это не есть хорошо... Вот так вот.

В том же Дейтеле описан неплохой алгоритм, который достаточно легко реализовать, попробуй.

А вообще это задача на рекурсию с возвратом.

[Joe Dering]

Рекурсивно решать или нет, все равно в основе решения этой задачи перебор. А рекурсия получается естественно, так-как посик идет по дереву кандидатов, так что каждая из его вершин приходится один раз. Это позволяет если найдено и должным образом зафиксировано одно решение, просто перейту к следующему кандидату, предлагаемому процессом полного перебора как в программе выше. Общая схема приблизительно такая.

void try(int i)
{
for ( int k = 0 to SQUARE_COUNT )
{
выбор к-го кандидата;
если подходит, записываем;
if ( i < SQUARE_COUNT )
try i+1);
}
}

Приблизительно так!
Вообще посмотрите в прекрасной статье Вирта "Program Development by Stepwise Refinement", классическая статья в программировании.
Удачи.

[nm]

посик по дереву кандидатов ходит ? )
а кандидаты не жалуются ????

а так в принципе алгоритм именно такой )))

могу предложить другую более интерестную модификацию. Написать параллельный алгоритм для ее решения, который решает ее за (наи)меньшее количество времени