首页 > 编程语言 > 详细

Jeff Somers's N Queens Solutions 最快的n皇后算法

时间:2015-03-30 15:53:01      阅读:794      评论:0      收藏:0      [点我收藏+]
  1 /*  Jeff Somers
  2 *
  3 *  Copyright (c) 2002
  4 *
  5 *  jsomers@alumni.williams.edu
  6 *  or
  7 *  allagash98@yahoo.com
  8 *
  9 *  April, 2002
 10 * 
 11 *  Program:  nq
 12 * 
 13 *  Program to find number of solutions to the N queens problem.
 14 *  This program assumes a twos complement architecture.
 15 *
 16 *  For example, you can arrange 4 queens on 4 x 4 chess so that
 17 *  none of the queens can attack each other:
 18 *
 19 *  Two solutions:
 20 *     _ Q _ _        _ _ Q _
 21 *     _ _ _ Q        Q _ _ _
 22 *     Q _ _ _        _ _ _ Q
 23 *     _ _ Q _    and _ Q _ _
 24 *   
 25 *  Note that these are separate solutions, even though they
 26 *  are mirror images of each other.
 27 *
 28 *  Likewise, a 8 x 8 chess board has 92 solutions to the 8 queens
 29 *  problem.
 30 *
 31 *  Command Line Usage:
 32 *
 33 *          nq N
 34 *
 35 *       where N is the size of the N x N board.  For example,
 36 *       nq 4 will find the 4 queen solution for the 4 x 4 chess
 37 *       board.
 38 *
 39 *  By default, this program will only print the number of solutions,
 40 *  not board arrangements which are the solutions.  To print the
 41 *  boards, uncomment the call to printtable in the Nqueen function.
 42 *  Note that printing the board arrangements slows down the program
 43 *  quite a bit, unless you pipe the output to a text file:
 44 *
 45 *  nq 10 > output.txt
 46 *
 47 *
 48 *  The number of solutions for the N queens problems are known for
 49 *  boards up to 23 x 23.  With this program, I‘ve calculated the
 50 *  results for boards up to 21 x 21, and that took over a week on
 51 *  an 800 MHz PC.  The algorithm is approximated O(n!) (i.e. slow),
 52 *  and calculating the results for a 22 x 22 board will take about 8.5
 53 *  times the amount of time for the 21 x 21 board, or over 8 1/2 weeks.
 54 *  Even with a 10 GHz machine, calculating the results for a 23 x 23
 55 *  board would take over a month.  Of course, setting up a cluster of
 56 *  machines (or a distributed client) would do the work in less time.
 57 * 
 58 *  (from Sloane‘s On-Line Encyclopedia of Integer Sequences,
 59 *   Sequence A000170
 60 *   http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000170
 61 *   )
 62 *
 63 *   Board Size:       Number of Solutions to          Time to calculate
 64 *   (length of one        N queens problem:              on 800MHz PC
 65 *    side of N x N                                    (Hours:Mins:Secs)
 66 *    chessboard)
 67 *
 68 *     1                                  1                    n/a
 69 *     2                                  0                   < 0 seconds
 70 *     3                                  0                   < 0 seconds
 71 *     4                                  2                   < 0 seconds
 72 *     5                                 10                   < 0 seconds
 73 *     6                                  4                   < 0 seconds
 74 *     7                                 40                   < 0 seconds
 75 *     8                                 92                   < 0 seconds
 76 *     9                                352                   < 0 seconds
 77 *    10                                724                   < 0 seconds
 78 *    11                               2680                   < 0 seconds
 79 *    12                              14200                   < 0 seconds
 80 *    13                              73712                   < 0 seconds
 81 *    14                             365596                  00:00:01
 82 *    15                            2279184                  00:00:04
 83 *    16                           14772512                  00:00:23
 84 *    17                           95815104                  00:02:38
 85 *    18                          666090624                  00:19:26
 86 *    19                         4968057848                  02:31:24
 87 *    20                        39029188884                  20:35:06
 88 *    21                       314666222712                 174:53:45
 89 *    22                      2691008701644                     ?
 90 *    23                     24233937684440                     ?
 91 *    24                                  ?                     ?
 92 */
 93 
 94 #include <stdio.h>
 95 #include <stdlib.h>
 96 #include <time.h>
 97 
 98 /*
 99 Notes on MAX_BOARDSIZE:
100 
101 A 32 bit unsigned long is sufficient to hold the results for an 18 x 18
102 board (666090624 solutions) but not for a 19 x 19 board (4968057848 solutions).
103 
104 In Win32, I use a 64 bit variable to hold the results, and merely set the
105 MAX_BOARDSIZE to 21 because that‘s the largest board for which I‘ve
106 calculated a result.
107 
108 Note: a 20x20 board will take over 20 hours to run on a Pentium III 800MHz,
109 while a 21x21 board will take over a week to run on the same PC.
110 
111 On Unix, you could probably change the type of g_numsolutions from unsigned long
112 to unsigned long long, or change the code to use two 32 bit ints to store the
113 results for board sizes 19 x 19 and up.
114 */
115 
116 #ifdef WIN32
117 
118 #define MAX_BOARDSIZE 21
119 typedef unsigned __int64 SOLUTIONTYPE;
120 
121 #else
122 
123 #define MAX_BOARDSIZE 18
124 typedef unsigned long SOLUTIONTYPE;
125 
126 #endif
127 
128 #define MIN_BOARDSIZE 2
129 
130 SOLUTIONTYPE g_numsolutions = 0;
131 
132 
133 /* Print a chess table with queens positioned for a solution */
134 /* This is not a critical path function & I didn‘t try to optimize it. */
135 void printtable(int boardsize, int* aQueenBitRes, SOLUTIONTYPE numSolution)
136 {
137     int i, j, k, row;
138 
139     /*  We only calculated half the solutions, because we can derive
140     the other half by reflecting the solution across the "Y axis". */
141     for (k = 0; k < 2; ++k)
142     {
143 #ifdef WIN32
144         printf("*** Solution #: %I64d ***\n", 2 * numSolution + k - 1);
145 #else
146         printf("*** Solution #: %d ***\n", 2 * numSolution + k - 1);
147 #endif
148         for ( i = 0; i < boardsize; i++)
149         {
150             unsigned int bitf;
151             /*
152             Get the column that was set (i.e. find the
153             first, least significant, bit set).
154             If aQueenBitRes[i] = 011010b, then
155             bitf = 000010b
156             */
157             bitf = aQueenBitRes[i];
158 
159             row = bitf ^ (bitf & (bitf - 1)); /* get least significant bit */
160             for ( j = 0; j < boardsize; j++)
161             {
162                 /* keep shifting row over to the right until we find the one ‘1‘ in
163                 the binary representation.  There will only be one ‘1‘. */
164                 if (0 == k && ((row >> j) & 1))
165                 {
166                     printf("Q ");
167                 }
168                 else if (1 == k && (row & (1 << (boardsize - j - 1)))) /* this is the board reflected across the "Y axis" */
169                 {
170                     printf("Q ");
171                 }
172                 else
173                 {
174                     printf(". ");
175                 }
176             }
177             printf("\n");
178         }
179         printf("\n");
180     }
181 }
182 
183 
184 /* The function which calculates the N queen solutions.
185 We calculate one-half the solutions, then flip the results over
186 the "Y axis" of the board.  Every solution can be reflected that
187 way to generate another unique solution (assuming the board size
188 isn‘t 1 x 1).  That‘s because a solution cannot be symmetrical
189 across the Y-axis (because you can‘t have two queens in the same
190 horizontal row).  A solution also cannot consist of queens
191 down the middle column of a board with an odd number of columns,
192 since you can‘t have two queens in the same vertical row.
193 
194 This is a backtracking algorithm.  We place a queen in the top
195 row, then note the column and diagonals it occupies.  We then
196 place a queen in the next row down, taking care not to place it
197 in the same column or diagonal.  We then update the occupied
198 columns & diagonals & move on to the next row.  If no position
199 is open in the next row, we back track to the previous row & move
200 the queen over to the next available spot in its row & the process
201 starts over again.
202 */
203 void Nqueen(int board_size)
204 {
205     int aQueenBitRes[MAX_BOARDSIZE]; /* results */
206     int aQueenBitCol[MAX_BOARDSIZE]; /* marks colummns which already have queens */
207     int aQueenBitPosDiag[MAX_BOARDSIZE]; /* marks "positive diagonals" which already have queens */
208     int aQueenBitNegDiag[MAX_BOARDSIZE]; /* marks "negative diagonals" which already have queens */
209     int aStack[MAX_BOARDSIZE + 2]; /* we use a stack instead of recursion */
210     register int* pnStack;
211 
212 
213     register int numrows = 0; /* numrows redundant - could use stack */
214     register unsigned int lsb; /* least significant bit */
215     register unsigned int bitfield; /* bits which are set mark possible positions for a queen */
216     int i;
217     int odd = board_size & 1; /* 0 if board_size even, 1 if odd */
218     int board_minus = board_size - 1; /* board size - 1 */
219     int mask = (1 << board_size) - 1; /* if board size is N, mask consists of N 1‘s */
220 
221 
222     /* Initialize stack */
223     aStack[0] = -1; /* set sentinel -- signifies end of stack */
224 
225     /* NOTE: (board_size & 1) is true iff board_size is odd */
226     /* We need to loop through 2x if board_size is odd */
227     for (i = 0; i < (1 + odd); ++i)
228     {
229         /* We don‘t have to optimize this part; it ain‘t the
230         critical loop */
231         bitfield = 0;
232         if (0 == i)
233         {
234             /* Handle half of the board, except the middle
235             column. So if the board is 5 x 5, the first
236             row will be: 00011, since we‘re not worrying
237             about placing a queen in the center column (yet).
238             */
239             int half = board_size>>1; /* divide by two */
240             /* fill in rightmost 1‘s in bitfield for half of board_size
241             If board_size is 7, half of that is 3 (we‘re discarding the remainder)
242             and bitfield will be set to 111 in binary. */
243             bitfield = (1 << half) - 1;
244             pnStack = aStack + 1; /* stack pointer */
245 
246             aQueenBitRes[0] = 0;
247             aQueenBitCol[0] = aQueenBitPosDiag[0] = aQueenBitNegDiag[0] = 0;
248         }
249         else
250         {
251             /* Handle the middle column (of a odd-sized board).
252             Set middle column bit to 1, then set
253             half of next row.
254             So we‘re processing first row (one element) & half of next.
255             So if the board is 5 x 5, the first row will be: 00100, and
256             the next row will be 00011.
257             */
258             bitfield = 1 << (board_size >> 1);
259             numrows = 1; /* prob. already 0 */
260 
261             /* The first row just has one queen (in the middle column).*/
262             aQueenBitRes[0] = bitfield;
263             aQueenBitCol[0] = aQueenBitPosDiag[0] = aQueenBitNegDiag[0] = 0;
264             aQueenBitCol[1] = bitfield;
265 
266             /* Now do the next row.  Only set bits in half of it, because we‘ll
267             flip the results over the "Y-axis".  */
268             aQueenBitNegDiag[1] = (bitfield >> 1);
269             aQueenBitPosDiag[1] = (bitfield << 1);
270             pnStack = aStack + 1; /* stack pointer */
271             *pnStack++ = 0; /* we‘re done w/ this row -- only 1 element & we‘ve done it */
272             bitfield = (bitfield - 1) >> 1; /* bitfield -1 is all 1‘s to the left of the single 1 */
273         }
274 
275         /* this is the critical loop */
276         for (;;)
277         {
278             /* could use
279             lsb = bitfield ^ (bitfield & (bitfield -1));
280             to get first (least sig) "1" bit, but that‘s slower. */
281             lsb = -((signed)bitfield) & bitfield; /* this assumes a 2‘s complement architecture */
282             if (0 == bitfield)
283             {
284                 bitfield = *--pnStack; /* get prev. bitfield from stack */
285                 if (pnStack == aStack) { /* if sentinel hit.... */
286                     break ;
287                 }
288                 --numrows;
289                 continue;
290             }
291             bitfield &= ~lsb; /* toggle off this bit so we don‘t try it again */
292 
293             aQueenBitRes[numrows] = lsb; /* save the result */
294             if (numrows < board_minus) /* we still have more rows to process? */
295             {
296                 int n = numrows++;
297                 aQueenBitCol[numrows] = aQueenBitCol[n] | lsb;
298                 aQueenBitNegDiag[numrows] = (aQueenBitNegDiag[n] | lsb) >> 1;
299                 aQueenBitPosDiag[numrows] = (aQueenBitPosDiag[n] | lsb) << 1;
300                 *pnStack++ = bitfield;
301                 /* We can‘t consider positions for the queen which are in the same
302                 column, same positive diagonal, or same negative diagonal as another
303                 queen already on the board. */
304                 bitfield = mask & ~(aQueenBitCol[numrows] | aQueenBitNegDiag[numrows] | aQueenBitPosDiag[numrows]);
305                 continue;
306             }
307             else
308             {
309                 /* We have no more rows to process; we found a solution. */
310                 /* Comment out the call to printtable in order to print the solutions as board position*/
311                 /* printtable(board_size, aQueenBitRes, g_numsolutions + 1);  */
312                 ++g_numsolutions;
313                 bitfield = *--pnStack;
314                 --numrows;
315                 continue;
316             }
317         }
318     }
319 
320     /* multiply solutions by two, to count mirror images */
321     g_numsolutions *= 2;
322 }
323 
324 /* Print the results at the end of the run */
325 void printResults(time_t* pt1, time_t* pt2)
326 {
327     double secs;
328     int hours , mins, intsecs;
329 
330     printf("End: \t%s", ctime(pt2));
331     secs = difftime(*pt2, *pt1);
332     intsecs = (int)secs;
333     printf("Calculations took %d second%s.\n", intsecs, (intsecs == 1 ? "" : "s"));
334 
335     /* Print hours, minutes, seconds */
336     hours = intsecs/3600;
337     intsecs -= hours * 3600;
338     mins = intsecs/60;
339     intsecs -= mins * 60;
340     if (hours > 0 || mins > 0)
341     {
342         printf("Equals ");
343         if (hours > 0)
344         {
345             printf("%d hour%s, ", hours, (hours == 1) ? "" : "s");
346         }
347         if (mins > 0)
348         {          
349             printf("%d minute%s and ", mins, (mins == 1) ? "" : "s");
350         }
351         printf("%d second%s.\n", intsecs, (intsecs == 1 ? "" : "s"));
352 
353     }
354 }
355 
356 /* main routine for N Queens program.*/
357 int main(int argc, char** argv)
358 {
359     time_t t1, t2;
360     int boardsize;
361 
362     if (argc != 2) {
363         printf("N Queens program by Jeff Somers.\n");
364         printf("\tallagash98@yahoo.com or jsomers@alumni.williams.edu\n");
365         printf("This program calculates the total number of solutions to the N Queens problem.\n");
366         printf("Usage: nq <width of board>\n"); /* user must pass in size of board */
367         return 0;
368     }
369 
370     boardsize = atoi(argv[1]);
371 
372     /* check size of board is within correct range */
373     if (MIN_BOARDSIZE > boardsize || MAX_BOARDSIZE < boardsize)
374     {
375         printf("Width of board must be between %d and %d, inclusive.\n",
376             MIN_BOARDSIZE, MAX_BOARDSIZE );
377         return 0;
378     }
379 
380     time(&t1);
381     printf("N Queens program by Jeff Somers.\n");
382     printf("\tallagash98@yahoo.com or jsomers@alumni.williams.edu\n");
383     printf("Start: \t %s", ctime(&t1));
384 
385     Nqueen(boardsize); /* find solutions */
386     time(&t2);
387 
388     printResults(&t1, &t2);
389 
390     if (g_numsolutions != 0)
391     {
392 #ifdef WIN32
393         printf("For board size %d, %I64d solution%s found.\n", boardsize, g_numsolutions, (g_numsolutions == 1 ? "" : "s"));
394 #else
395         printf("For board size %d, %d solution%s found.\n", boardsize, g_numsolutions, (g_numsolutions == 1 ? "" : "s"));
396 #endif
397     }
398     else
399     {
400         printf("No solutions found.\n");
401     }
402 
403     return 0;
404 }

 

Jeff Somers's N Queens Solutions 最快的n皇后算法

原文:http://www.cnblogs.com/lxd2502/p/4378011.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!