001      // Author Malte Pagel
002      
003      // main.c
004      
005      #include <stdio.h>
006      #include <stdlib.h>
007      
008      
009      void show_all(int *);
010      int set_queen(int *, int);
011      int possible(int *, int);
012      
013      
014      
015      int num_cols = 8;
016      
017      int all_solutions = 0;
018      
019      
020      
021      void show_all ( int *cols ) {
022              int x, y;
023              printf("\t");
024              for ( y = 1; y <= num_cols; y++ ) {
025                      for ( x = 0; x < num_cols; x++ )
026                              if ( cols[x] == y )
027                                      printf(" Q ");
028                              else
029                                      printf(" . ");
030                      printf("\n\t");
031              }
032      }
033      
034      
035      int possible ( int *cols, int queen ) {
036              int i;
037              int col = num_cols - queen;
038      
039              for ( i = (col + 1); i < num_cols; i++ ) {
040                      if ( cols[col] == cols[i] )                                     // horizontal
041                              return 0;
042                      if ( abs(col - i) == abs(cols[col] - cols[i]) )           // diagonal
043                              return 0;
044              }
045      
046              return 1;
047      }
048      
049      int set_queen ( int *cols, int which ) {
050              int queen, suggest = 1;
051              static int count = 1;
052      
053              queen = num_cols - which;
054      
055              while ( suggest <= num_cols ) {
056                      cols[which] = suggest;
057                      if ( possible(cols, queen) )
058                              if ( which ) {
059                                      if ( set_queen(cols, (which-1)) )
060                                              return 1;
061                              }
062                              else {
063                                      if ( all_solutions )
064                                              printf("\nSolution %2d:\n", count++);
065                                      show_all(cols);
066                                      if ( !all_solutions )
067                                              return 1;
068                              }
069                      suggest++;
070              }
071      
072              cols[which] = 0;
073              return 0;
074      }
075      
076      
077      
078      
079      int main ( int argc, char *argv[] ) {
080              printf("\n\n\t%d queens with no two queens attacking each other\n\n", num_cols);
081      
082              // *cols is NOT a binary matrix in two dimensions;
083              // since it is known that every column owns one queen,
084              // row position of queen is stored in every value of *cols
085              int *cols, i;
086              char c;
087      
088              cols = malloc(num_cols * sizeof(int *));
089      
090              for ( i = 0; i < num_cols; i++ )
091                      cols[i] = 0;
092      
093              set_queen(cols, (num_cols-1));
094      
095              
096              printf("\nShow all solutions? [y/n]\n");
097              scanf("%c", &c);
098              if ( c == 'y' ) {
099                      all_solutions = 1;
100                      printf("\nHow many rows resp. columns? [more than 8 could be unhealthy]\n");
101                      scanf("%d", &num_cols);
102                      cols = malloc(num_cols * sizeof(int *));
103                      for ( i = 0; i < num_cols; i++ )
104                              cols[i] = 0;
105                      set_queen(cols, (num_cols-1));
106              }
107      
108              free(cols);
109      
110      
111              printf("\n\n");
112      
113              return EXIT_SUCCESS;
114      }
115