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
:mad: ------------------
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 :p

[Aram Hambardzumyan]

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

[Eddi]

Originally posted by MuZe:
ah.. ja ete znaju :)

palaji tak
E1,A2,H3,f4,C5,G6,B7,D8 :p A posle etogo mogesh' ciklicheski menyat' poloski doski both vertically and horizontally i poluchish' vse vozmognye varianty :cool:

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!!! :eek:

[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!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! :agree: :agree: :agree: :agree: :agree:

[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]

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

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

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