PDA

View Full Version : Checkmate!

FearOfTheDark
04-20-2003, 06:08 AM
How do you put 8 queens on a chessboard so that they won't capture each other?

Magos
04-20-2003, 07:10 AM
Being on a programming forum and all, you could write a program that finds the answer for you...
Or look below:

minesweeper
04-20-2003, 07:38 AM
Won't the top and bottom-most queens capture each other?

golfinguy4
04-20-2003, 07:44 AM
Put on 8 kings so they're busy?

Put 4 queens on opposite sides of the board and offset them 1 square to the side. At least using the already posted board, that works.

BMJ
04-20-2003, 07:48 AM
I don't think it's possible.

minesweeper
04-20-2003, 07:49 AM
Golfinguy,

Do you mean having 4 queens on the same vertical line? Because that clearly won't work.

XSquared
04-20-2003, 07:59 AM
This one actually works. (There are 92 working solutions)

vasanth
04-20-2003, 08:54 AM
You could create a program to find the solution using backtracking.... Similar to solving a maze problem.. I have to use something like this when i start coding my chess games single player part..

Magos
04-20-2003, 11:18 AM
Originally posted by minesweeper
Won't the top and bottom-most queens capture each other?
Gee, how could I miss that one???
And I thought I checked em all.... :(

golfinguy4
04-20-2003, 04:20 PM
Originally posted by minesweeper
Golfinguy,

Do you mean having 4 queens on the same vertical line? Because that clearly won't work.

Never mind. I was thinking that 4 of the queens were on the same team.

XSquared
04-20-2003, 06:54 PM
And if you want how I calculated it, here ya go.

Warning
This code is uncommented, and basically contest-style code.

#pragma warning( disable: 4530 )

#include <fstream>

using namespace std;

#define MAXSIZE 13

bool col[ MAXSIZE ];
bool updiag[ MAXSIZE * 2 ];
bool downdiag[ MAXSIZE * 2 ];

ifstream in("checker.in");
ofstream out("checker.out");

int n = 0;
int numoutputed = 0;

void outputsoln( int *row )
{

for( int i = 0; i < n; i++ ) {

if( i != 0 ) out<<" ";

out<<row[i] + 1;

}

out<<endl;

}

int calcnum( int i, int *row )
{
int sum = 0;

if( i == n ) {

outputsoln( row );
return 1;

}

for( int j = 0; j < n; j++ ) {

if( !col[ j ] && !updiag[ i + j ] && !downdiag[ i - j + n ] ) {

col[ j ] = true;
updiag[ i + j ] = true;
downdiag[ i - j + n ] = true;
row[i] = j;

sum += calcnum( i + 1, row );

col[ j ] = false;
updiag[ i + j ] = false;
downdiag[ i - j + n ] = false;

}

}

return sum;

}

int main( void )
{
int rows[ MAXSIZE ];

in>>n;

out<<calcnum( 0, rows )<<endl;

return 0;
}