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       * Default; can be changed by user for to get squares of different size
016       */
017      int num_cols = 8;
018      /*
019       * Quasi boolean
020       */
021      int all_solutions = 0;
022      
023      
024      /*
025       * Displays a solution; shows Queen as 'Q' and empty field as '.'
026       */
027      void show_all ( int *cols ) {
028              int x, y;
029              printf("\t");
030              for ( y = 1; y <= num_cols; y++ ) {
031                      for ( x = 0; x < num_cols; x++ )
032                              if ( cols[x] == y )
033                                      printf(" Q ");
034                              else
035                                      printf(" . ");
036                      printf("\n\t");
037              }
038      }
039      
040      /*
041       * Prooves if a queen can be set.
042       * Does NOT proove columns (it is known that every column can only own one queen).
043       * Prooves only against already set columns.
044       */
045      int possible ( int *cols, int queen ) {
046              int i;
047              int col = num_cols - queen;
048      
049              for ( i = (col + 1); i < num_cols; i++ ) {
050                      if ( cols[col] == cols[i] )                                     // horizontal
051                              return 0;
052                      if ( abs(col - i) == abs(cols[col] - cols[i]) )           // diagonal
053                              return 0;
054              }
055      
056              return 1;
057      }
058      /*
059       * Recursive function.
060       * Tries every row in every column:
061       *      - if a queen attacks an already set queen, try was bad.
062       *      - if she doesn't, but the next queen attacks an already set queen, try also was bad.
063       *      - if queen is allowed and there are no columns left, try was good.
064       * When variable 'all_solutions' is not set, function stops after finding first solution
065       */
066      int set_queen ( int *cols, int which ) {
067              int queen, suggest = 1;
068              static int count = 1;
069      
070              queen = num_cols - which;
071      
072              while ( suggest <= num_cols ) {
073                      cols[which] = suggest;
074                      if ( possible(cols, queen) )
075                              if ( which ) {
076                                      if ( set_queen(cols, (which-1)) )
077                                              return 1;
078                              }
079                              else {
080                                      if ( all_solutions )
081                                              printf("\nSolution %2d:\n", count++);
082                                      show_all(cols);
083                                      if ( !all_solutions )
084                                              return 1;
085                              }
086                      suggest++;
087              }
088      
089              cols[which] = 0;
090              return 0;
091      }
092      
093      
094      
095      /*
096       * Initialization:
097       * Searches for one solution on chess table (num_cols = 8).
098       * Asks user for number of columns ( = number of rows, table is square).
099       * Allocates memory and starts 'set_queen()' with first (i.e. most right) column.
100       */
101      int main ( int argc, char *argv[] ) {
102              printf("\n\n\t%d queens with no two queens attacking each other\n\n", num_cols);
103      
104              // *cols is NOT a binary matrix in two dimensions;
105              // since it is known that every column owns one queen,
106              // row position of queen is stored in every value of *cols
107              int *cols, i;
108              char c;
109      
110              cols = malloc(num_cols * sizeof(int *));
111      
112              for ( i = 0; i < num_cols; i++ )
113                      cols[i] = 0;
114      
115              set_queen(cols, (num_cols-1));
116      
117              
118              printf("\nShow all solutions? [y/n]\n");
119              scanf("%c", &c);
120              if ( c == 'y' ) {
121                      all_solutions = 1;
122                      printf("\nHow many rows resp. columns? [more than 8 could be unhealthy]\n");
123                      scanf("%d", &num_cols);
124                      cols = malloc(num_cols * sizeof(int *));
125                      for ( i = 0; i < num_cols; i++ )
126                              cols[i] = 0;
127                      set_queen(cols, (num_cols-1));
128              }
129      
130              free(cols);
131      
132      
133              printf("\n\n");
134      
135              return EXIT_SUCCESS;
136      }
137