Inhalt | Code | Beispiel |
C | Javascript | Kommentare | Zeilennummern | Midnight |
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