Introduction
The n queens puzzle is the problem of placing n chess queens on an n*n chessboard so that no two queens attack each other.
The Program
queens_ori.c
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
/**
* The n queens puzzle is the problem of
* placing n chess queens on an n×n chessboard
* so that no two queens attack each other.
*/
// define some values to shorten the code
// status message and params
// printf(statmsg, statparam); will become
// printf("there are %d queens in a %d x %d chessboard\n\n answer(s): \n\n", number_of_queens, number_of_queens, number_of_queens);
#define statmsg "there are %d queens in a %d x %d chessboard\n\n answer(s): \n\n"
#define statparam number_of_queens, number_of_queens, number_of_queens
// answer message and params
#define ansmsg "put col[%d] queen to row %d\n"
#define ansparam outIdx, col[outIdx]
int number_of_queens; // n queens in nxn chessboard
// note: don't too large (ex, over 25)
int *col; // chessboard
FILE *outptr; // output file
int cnt; // result count
// function to solve this problem
void queens( int currentCol );
// function to determing whether the status is valid
bool promising( int currentCol );
int main()
{
cnt = 0;
printf("please enter the number of queens:\n");
scanf("%d", &number_of_queens);
// col[0] not used, start from col[1]
col = (int*) malloc ((number_of_queens+1)*sizeof(int));
outptr = fopen("QueenSol.txt", "w" );
printf(statmsg, statparam);
fprintf(outptr, statmsg, statparam);
// call function to solve problem
// pass 0 into it but it will then start from 1
queens( 0 );
if (cnt == 0) {
printf(" no result\n\n");
fprintf(outptr, " no result\n\n");
}
fclose( outptr );
free(col);
system("PAUSE");
return 0;
}
void queens( int currentCol )
{
int row; // row index to test
int outIdx; // index for output result
if( promising(currentCol) ) // if valid
{
if( currentCol == number_of_queens ) // output if at latest col
{
cnt++;
for( outIdx = 1; outIdx <= number_of_queens; outIdx++ )
{
printf(ansmsg, ansparam);
fprintf(outptr, ansmsg, ansparam);
}
printf("\n\n");
fprintf(outptr, "\n\n");
}
// call function recursively if not latest col
else
{
for(row = 1; row <= number_of_queens; row++ ) // test next col from row 1 to row n
{
col[currentCol + 1] = row;
queens( currentCol + 1 );
}
}
}
}
// check whether current stats is valid
bool promising( int currentCol )
{
int idx = 1; // loop index
bool isValid = true; // is valid? default to true
// test whether previous queens will attack current queen
while( (idx < currentCol) && isValid )
{
// found invalid status
// in the same row
// or diagonal
if( (col[currentCol] == col[idx])
|| (abs( col[currentCol] - col[idx]) == currentCol - idx) )
{
isValid = false; // set to invalid, stop loop
}
idx++; // increase index and contiune
}
return isValid;
}
The Result
Reference
http://en.wikipedia.org/wiki/Eight_queens_puzzle
Download
The files are at github
https://github.com/benbai123/C_Cplusplus_Practice/tree/master/C_Algorithm/N_Quenes
