Update NQueens program. This program can be a benchmark test for seed balancer
[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         }
57     }
58     //CkPrintf(" level = %d\n", current_row+1);
59 }
60
61 void NQueen::sequentialSolve( QueenState *m)
62 {
63
64     int aQueenBitRes[MAX_BOARDSIZE];
65     int aQueenBitCol[MAX_BOARDSIZE];
66     int aQueenBitPosDiag[MAX_BOARDSIZE];
67     int aQueenBitNegDiag[MAX_BOARDSIZE];
68     int aStack[MAX_BOARDSIZE + 2]; /* we use a stack instead of recursion */
69     int n = m->numrows;
70     register int* pnStack;
71     register int numrows = m->numrows; /* numrows redundant - could use stack */
72     register unsigned int lsb; /* least significant bit */
73     register unsigned int bitfield; /* bits which are set mark possible positions for a queen */
74     int board_minus = numQueens - 1; /* board size - 1 */
75     int mask = (1 << numQueens) - 1; /* if board size is N, mask consists of N 1's */
76     aStack[0] = -1;
77     
78     pnStack = aStack + 1;
79
80     aQueenBitCol[n] = m->aQueenBitCol;
81     aQueenBitNegDiag[n] = m->aQueenBitNegDiag;
82     aQueenBitPosDiag[n] = m->aQueenBitPosDiag;
83     bitfield = mask & ~(m->aQueenBitCol | m->aQueenBitNegDiag | m->aQueenBitPosDiag);
84     /* this is the critical loop */
85     for (;;)
86     {
87         /* could use 
88          * lsb = bitfield ^ (bitfield & (bitfield -1)); 
89          * to get first (least sig) "1" bit, but that's slower. */
90         lsb = -((signed)bitfield) & bitfield; /* this assumes a 2's complement architecture */
91         if (0 == bitfield)
92         {
93             bitfield = *--pnStack; /* get prev. bitfield from stack */
94             if (pnStack == aStack) { /* if sentinel hit.... */
95                 break ;
96             }
97             --numrows;
98             continue;
99         }
100         bitfield &= ~lsb; /* toggle off this bit so we don't try it again */
101
102         aQueenBitRes[numrows] = lsb; /* save the result */
103         if (numrows < board_minus) /* we still have more rows to process? */
104         {
105             n = numrows++;
106             aQueenBitCol[numrows] = aQueenBitCol[n] | lsb;
107             aQueenBitNegDiag[numrows] = (aQueenBitNegDiag[n] | lsb) >> 1;
108             aQueenBitPosDiag[numrows] = (aQueenBitPosDiag[n] | lsb) << 1;
109             *pnStack++ = bitfield;
110             /* We can't consider positions for the queen which are in the same
111              * * column, same positive diagonal, or same negative diagonal as another
112              * queen already on the board. */
113             bitfield = mask & ~(aQueenBitCol[numrows] | aQueenBitNegDiag[numrows] | aQueenBitPosDiag[numrows]);
114             continue;
115         }
116         else{
117             /* printtable(board_size, aQueenBitRes, g_numsolutions + 1);  */
118             CProxy_counter(counterGroup).ckLocalBranch()->increment();
119             bitfield = *--pnStack;
120             --numrows;
121             continue;
122         }
123     }
124
125 }
126 void NQueen::printSolution(int queens[])
127 {
128 }
129
130 /*
131 void NQueen::pup(PUP::er &p)
132 {
133     p | current_row;
134     p | queenInWhichColum;
135 }
136 */