/* 8-queens.c Solve the eight queens problem using backtracking */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #include #include #define MAXCANDIDATES 100 /* max possible next extensions */ #define NMAX 100 /* maximum solution size */ bool finished = false; int solution_count; /* how many solutions are there? */ void process_solution(int a[], int k, int input) { solution_count ++; } int is_a_solution(int a[], int k, int n) { return (k == n); } void make_move(int a[], int k, int n) { } void unmake_move(int a[], int k, int n) { } /* What are possible elements of the next slot in the 8-queens problem? */ void construct_candidates(int a[], int k, int n, int c[], int *ncandidates) { int i, j; /* counters */ bool legal_move; /* might the move be legal? */ *ncandidates = 0; for (i = 1; i <= n; i++) { legal_move = true; for (j = 1; j < k; j++) { if (abs((k)-j) == abs(i-a[j])) { /* diagonal threat */ legal_move = false; } if (i == a[j]) { /* column threat */ legal_move = false; } } if (legal_move) { c[*ncandidates] = i; *ncandidates = *ncandidates + 1; } } } void backtrack(int a[], int k, int input) { int c[MAXCANDIDATES]; /* candidates for next position */ int ncandidates; /* next position candidate count */ int i; /* counter */ if (is_a_solution(a, k, input)) { process_solution(a, k, input); } else { k = k + 1; construct_candidates(a,k,input,c,&ncandidates); for (i = 0; i < ncandidates; i++) { a[k] = c[i]; make_move(a, k, input); backtrack(a, k, input); unmake_move(a, k, input); if (finished) { return; /* terminate early */ } } } } int main(void) { int a[NMAX]; /* solution vector */ int i; /* counter */ for (i = 1; i <= 10; i++) { solution_count = 0; backtrack(a, 0, i); printf("n=%d solution_count=%d\n", i, solution_count); } return 0; }