examples/charm++/barnes-charm: renamed variable in prototype to avoid compiler confusion
[charm.git] / examples / charm++ / NQueen / nqueen.C
1 #include "main.decl.h"
2 #include "nqueen.h"
3 #include "counter.h"
4
5 extern int numQueens;
6 extern CProxy_Main mainProxy;
7 extern int grainsize;
8 extern CkGroupID counterGroup;
9
10 NQueen::NQueen(CkMigrateMessage *msg) {}
11
12 NQueen::NQueen(QueenState *m)
13 {
14     int lsb;
15     int n = m->numrows;
16     int bitfield;// = m->bitfield;
17     int mask; 
18     int current_row = m->numrows+1;
19     QueenState *new_msg;
20     
21     mask = (1 << numQueens ) - 1;
22     bitfield = mask & ~(m->aQueenBitCol | m->aQueenBitNegDiag | m->aQueenBitPosDiag);
23
24     /*for all possible places in next row */
25     if(n == numQueens-1)
26     {
27         if(bitfield!=0){
28             CProxy_counter(counterGroup).ckLocalBranch()->increment();
29         }
30             return;
31     }
32     // the next step is reasonable. fire a new child
33     for(;;)
34     {
35     
36         if(bitfield == 0)
37         {
38             break;
39         }
40         lsb = -((signed)bitfield)&bitfield;
41         new_msg = new QueenState;
42         new_msg->aQueenBitRes = lsb;
43         new_msg->aQueenBitCol = m->aQueenBitCol | lsb;
44         new_msg->aQueenBitNegDiag = (m->aQueenBitNegDiag |lsb) >> 1;
45         new_msg->aQueenBitPosDiag = (m->aQueenBitPosDiag | lsb) << 1;
46         new_msg->numrows = current_row;
47         bitfield &= ~lsb;
48         if(current_row < grainsize)
49         {
50             //CkSetQueueing(new_msg, CK_QUEUEING_ILIFO);
51             CProxy_NQueen::ckNew(new_msg);
52         }else
53         {
54             //sequential solve
55             //thisProxy.sequentialSolve(new_msg);
56             sequentialSolve(new_msg);
57         }
58     }
59     //CkPrintf(" level = %d\n", current_row+1);
60 }
61
62 void NQueen::sequentialSolve( QueenState *m)
63 {
64
65     int aQueenBitRes[MAX_BOARDSIZE];
66     int aQueenBitCol[MAX_BOARDSIZE];
67     int aQueenBitPosDiag[MAX_BOARDSIZE];
68     int aQueenBitNegDiag[MAX_BOARDSIZE];
69     int aStack[MAX_BOARDSIZE + 2]; /* we use a stack instead of recursion */
70     int n = m->numrows;
71     register int* pnStack;
72     register int numrows = m->numrows; /* numrows redundant - could use stack */
73     register unsigned int lsb; /* least significant bit */
74     register unsigned int bitfield; /* bits which are set mark possible positions for a queen */
75     int board_minus = numQueens - 1; /* board size - 1 */
76     int mask = (1 << numQueens) - 1; /* if board size is N, mask consists of N 1's */
77     aStack[0] = -1;
78     
79     pnStack = aStack + 1;
80
81     aQueenBitCol[n] = m->aQueenBitCol;
82     aQueenBitNegDiag[n] = m->aQueenBitNegDiag;
83     aQueenBitPosDiag[n] = m->aQueenBitPosDiag;
84     bitfield = mask & ~(m->aQueenBitCol | m->aQueenBitNegDiag | m->aQueenBitPosDiag);
85     /* this is the critical loop */
86     for (;;)
87     {
88         /* could use 
89          * lsb = bitfield ^ (bitfield & (bitfield -1)); 
90          * to get first (least sig) "1" bit, but that's slower. */
91         lsb = -((signed)bitfield) & bitfield; /* this assumes a 2's complement architecture */
92         if (0 == bitfield)
93         {
94             bitfield = *--pnStack; /* get prev. bitfield from stack */
95             if (pnStack == aStack) { /* if sentinel hit.... */
96                 break ;
97             }
98             --numrows;
99             continue;
100         }
101         bitfield &= ~lsb; /* toggle off this bit so we don't try it again */
102
103         aQueenBitRes[numrows] = lsb; /* save the result */
104         if (numrows < board_minus) /* we still have more rows to process? */
105         {
106             n = numrows++;
107             aQueenBitCol[numrows] = aQueenBitCol[n] | lsb;
108             aQueenBitNegDiag[numrows] = (aQueenBitNegDiag[n] | lsb) >> 1;
109             aQueenBitPosDiag[numrows] = (aQueenBitPosDiag[n] | lsb) << 1;
110             *pnStack++ = bitfield;
111             /* We can't consider positions for the queen which are in the same
112              * * column, same positive diagonal, or same negative diagonal as another
113              * queen already on the board. */
114             bitfield = mask & ~(aQueenBitCol[numrows] | aQueenBitNegDiag[numrows] | aQueenBitPosDiag[numrows]);
115             continue;
116         }
117         else{
118             /* printtable(board_size, aQueenBitRes, g_numsolutions + 1);  */
119             CProxy_counter(counterGroup).ckLocalBranch()->increment();
120             bitfield = *--pnStack;
121             --numrows;
122             continue;
123         }
124     }
125
126 }
127 void NQueen::printSolution(int queens[])
128 {
129 }
130
131 /*
132 void NQueen::pup(PUP::er &p)
133 {
134     p | current_row;
135     p | queenInWhichColum;
136 }
137 */