Update NQueens program. This program can be a benchmark test for seed balancer
[charm.git] / examples / charm++ / NQueen / main.C
1 /*
2  * N Queen solver 
3  * Feb 1st
4  *
5  * Copyright by PPL
6  * problem report sun51@uiuc.edu
7 */
8 #include "main.decl.h"
9 #include "main.h"
10 #include "nqueen.h"
11 #include "counter.h"
12
13 Main::Main(CkArgMsg* msg)
14 {
15
16     //CkPrintf(" Usage: nqueen Num\n");
17
18     numQueens = 5;
19     grainsize = 3;
20     if(msg->argc > 2)
21     {
22         numQueens = atoi(msg->argv[1]);
23         grainsize = atoi(msg->argv[2]);   
24     }
25     delete msg;
26
27     CkPrintf(" Usage: nqueen numQueen grainsize (%d, g=%d, np=%d)\n", numQueens, grainsize, CkNumPes());
28
29     /* timer */
30     mainhandle=thishandle;
31     
32     
33     int odd = numQueens&1;
34     int board_minus = numQueens - 1;
35     mask = (1<<numQueens) - 1;
36     int bitfield = 0;
37     int half = numQueens >> 1;
38     int numrows = 1;
39     int col;
40     int pos;
41     int neg;
42     int lsb;
43
44     bitfield  = (1 << half) -1;
45     for(;;)
46     {
47         if(bitfield == 0)
48             break;
49         lsb = -((signed)bitfield) & bitfield; 
50         QueenState *qmsg = new QueenState;
51         qmsg->aQueenBitRes= lsb;
52         qmsg->aQueenBitCol = 0|lsb;
53         qmsg->aQueenBitNegDiag = (0|lsb) >> 1;
54         qmsg->aQueenBitPosDiag = (0|lsb) << 1;
55         //qmsg->bitfield = mask & ~(qmsg->aQueenBitCol[numrows] | qmsg->aQueenBitNegDiag[numrows] | qmsg->aQueenBitPosDiag[numrows]);
56         qmsg->numrows = 1; 
57         //CkSetQueueing(qmsg, CK_QUEUEING_ILIFO);
58         CProxy_NQueen::ckNew(qmsg);
59         bitfield &= ~lsb;
60     }
61
62     if(odd == 1)
63     {
64         bitfield = 1 << (numQueens >> 1);
65         numrows = 1; /* prob. already 0 */
66         /* The first row just has one queen (in the middle column).*/
67         col = bitfield;
68         /* Now do the next row.  Only set bits in half of it, because we'll
69          * * * *                flip the results over the "Y-axis".  */
70         neg = (bitfield >> 1);
71         pos = (bitfield << 1);
72         bitfield = (bitfield - 1) >> 1;
73         for(;;)
74         {
75             if(bitfield == 0)
76                 break;
77             lsb = -((signed)bitfield) & bitfield; 
78
79             QueenState *qmsg = new QueenState;
80             qmsg->aQueenBitRes = lsb;
81             qmsg->aQueenBitCol = col|lsb;
82             qmsg->aQueenBitNegDiag = (neg|lsb)>>1;
83             qmsg->aQueenBitPosDiag = (pos|lsb)<<1;
84             qmsg->numrows = 2; 
85             //CkSetQueueing(qmsg, CK_QUEUEING_ILIFO);
86             CProxy_NQueen::ckNew(qmsg);
87             bitfield &= ~lsb;
88         }
89     }
90     starttimer = CkTimer();
91     counterGroup = counterInit();
92     CkStartQD(CkIndex_Main::Quiescence1((DUMMYMSG *)0), &mainhandle);
93 }
94
95 Main::Main(CkMigrateMessage* msg) {}
96
97 void Main::Quiescence1(DUMMYMSG *msg)
98 {
99     int numSolutions = CProxy_counter(counterGroup).ckLocalBranch()->getTotalCount();
100     double endtimer = CkTimer();
101     CkPrintf("There are %d Solutions to %d queens. Time=%f\n",
102         2*numSolutions, numQueens, endtimer-starttimer);
103     CkExit();
104 }
105
106 #include "main.def.h"