/
queens_ori.c
114 lines (96 loc) · 2.84 KB
/
queens_ori.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#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;
}