Verifying the 8-Queens


The 8-Queens problem in chess is to place 8 queens on a chess board such that none of the queens is threatening any of the others. A chess board is an 8 x 8 matrix of squares and queens may move any direction along a row, column or diagonal. The problem is to input the 8 columns of the queens on the rows of a chess board, with 1 being the first column and 8 being the last, e.g. 1 2 3 4 5 6 7 8 means the queens are along the diagonal, which would not be a valid solution.

Example 1:

Enter board configuration: 3 5 2 8 1 7 4 6
This is a valid configuration.

Example 2:
Enter board configuration: 1 8 2 5 3 7 4 6
This is NOT a valid configuration.

#include
#include

int board [8] [8];

bool isValid (int i, int j)
{
int count = 0;
for ( int k = 0; k < 8; k++ ) { if ( board [i] [k] == 1 ) count++; } for ( int k = 0; k < 8; k++ ) { if ( board [k] [j] == 1 ) count++; } int x = i; int y = j; while ( x != -1 && y != -1 ) { if ( board [x--] [y--] == 1 ) count++; } x = i + 1; y = j + 1; while ( x != 7 && y != 7 ) { if ( board [x++] [y++] == 1 ) count++; } if ( count == 3 ) return true; return false; } int main () { for ( int i = 0; i < 8; i++ ) { for ( int j = 0; j < 8; j++ ) board [i] [j] = 0; } printf ("Enter board configuration: "); int input; for ( int i = 0; i < 8; i++ ) { scanf ("%d", &input); board [i] [input - 1] = 1; } bool flag = true; for ( int i = 0; i < 8; i++ ) { for ( int j = 0; j < 8; j++ ) { if ( board [i] [j] == 1 ) { if ( isValid (i, j) == false ) { flag = false; i = j = 8; // break } } } } if ( flag ) printf("This is a valid configuration.\n"); else printf ("This is NOT a valid configuration.\n"); return 0; } [/sourcecode]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s