دانلود رایگان سوالات رشته جغرافیا ترم دوم 92-91
الگوریتم 8 وزیر
ادامه مطلب
# include
# include
# define MAXSIZE 8
class EightQueens
{
int m_size;
int m_solution_count;
int m_attempt_count;
int m_queen[MAXSIZE];
bool m_row_inuse[MAXSIZE];
bool m_diag_rise[MAXSIZE*2];
bool m_diag_fall[MAXSIZE*2];
public:
EightQueens(int size, bool is_alt) {
assert(size <= MAXSIZE);
m_size = size;
m_solution_count = ۰;
m_attempt_count = ۰;
for (int i = 0; i < m_size; i++) {
m_queen[i] = i;
m_row_inuse[i] = ۰;
}
for (int j = 0; j < m_size*2; j++) {
m_diag_rise[j] = ۰;
m_diag_fall[j] = ۰;
}
if (is_alt) SearchAlt(0);
else Search(0);
}
int GetSolutionCount() {
return m_solution_count;
}
int GetAttemptCount() {
return m_attempt_count;
}
private:
void SearchAlt(int col){
if (col == m_size) {
m_solution_count++;
return;
}
for (int row = 0; row < m_size; row++) {
m_attempt_count++;
if (m_row_inuse[row] == 0 && IsDiagValid(col, row)) {
m_queen[col] = row;
m_row_inuse[row] = ۱;
SetDiags(col, 1);
SearchAlt(col+1);
SetDiags(col, 0);
m_row_inuse[row] = ۰;
m_queen[col] = -۱;
}
}
}
void Search(int col) {
if (col == m_size) {
m_solution_count++;
return;
}
for (int i = col; i < m_size; i++) {
if (SwapQueenIfDiagValid(col, i)) {
Search(col+1);
UnSwapQueen(col, i);
}
}
}
void SwapQueenBasic(int i, int j) {
int hold = m_queen[i];
m_queen[i] = m_queen[j];
m_queen[j] = hold;
}
void SetDiags(int col, int val) {
assert(m_diag_rise[m_queen[col] + col]!= val);
m_diag_rise[m_queen[col] + col] = val;
assert(m_diag_fall[m_queen[col] - col + m_size]!= val);
m_diag_fall[m_queen[col] - col + m_size] = val;
}
bool IsDiagValid(int col, int row) {
return (m_diag_rise[row + col] == ۰ &&
m_diag_fall[row - col + m_size] == ۰);
}
bool SwapQueenIfDiagValid(int i, int j) {
m_attempt_count++;
if (IsDiagValid(i, m_queen[j])) {
SwapQueenBasic(i, j);
SetDiags(i, 1);
return true;
}
return false;
}
void UnSwapQueen(int i, int j) {
SetDiags(i, 0);
SwapQueenBasic(i, j);
}
};
void
do_work(bool is_alt)
{
int size = ۸;
EightQueens puzzle(size, is_alt);
int soln = puzzle.GetSolutionCount();
int attempt = puzzle.GetAttemptCount();
assert(size!= ۸ || soln == ۹۲);
const char* style = is_alt ? "cartesian": "permutation";
printf("EightQueens[%d] has %d solutions found in %5d attempts using %s search. \\n", size, soln, attempt, style);
}
int main()
{
printf("We should have 92 solutions for 8x8. \\n");
do_work(0);
do_work(1)
بسته آموزش حرفه ای مقاله نویسی ISI ویژه داوطلبین ارشد و دکتری