/******************************************************************/ /* */ /* Program: queens.c */ /* */ /* Description: */ /* */ /* This program finds all the possible ways that N queens can */ /* be placed on an NxN chessboard so that the queens cannot */ /* capture one another. The code makes no attemt to */ /* eliminate symmetrical solutions, so the number of solutions */ /* reported will always be higher than the actual number of */ /* distinct solutions. */ /* */ /* */ /* Algorithm and program by: Stefan Spaennare, Lund, Sweden */ /* */ /* E-mail: stefan@spaennare.se */ /* */ /* Latest update: 2003-02-19 */ /* */ /******************************************************************/ /********************************************************************************/ /* */ /* Notice */ /* ====== */ /* */ /* I make no warranties that this program is (1) free of errors, (2) consistent */ /* with any standard merchantability, or (3) meeting the requirements of a */ /* particular application. This software shall not, partly or as a whole, */ /* participate in a process, whose outcome can result in injury to a person or */ /* loss of property. It is solely designed for analytical work. Permission to */ /* use, copy and distribute is hereby granted without fee, providing that the */ /* header above including this notice appears in all copies. */ /* */ /* Stefan Spaennare */ /* */ /********************************************************************************/ #include #include #include #include #include double timetic=(double)(CLOCKS_PER_SEC); void printboard(ss,d,n) char *ss; int *d; int n; { int i,j,k,n2; n2=2*n; for (i=0; i 0) { d[i]++; k=0; do { k++; c=d[i]-d[k]; } while ((c != 0) && (abs(c) != abs(i-k))); if ((i == n) && (k == i)) { s++; printf("\n%6d\n\n",s); printboard(ss,d,n); } else if (k == i) { i++; } /* if */ while (d[i] == n) { d[i]=0; i--; } /* while */ } /* while */ timediff=clock()-time1; ftime=(double)(timediff)/timetic; printf("\n\n"); printf("Total: %6d %10.2f\n\n",s,ftime); } /* End */