Merge branch 'charm' of charmgit:charm into charm
[charm.git] / examples / charm++ / queens / pgm.C
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4
5 #include "charm++.h"
6
7 #include "pgm.h"
8 #include "Pgm.def.h"
9
10 #include "counter.h"
11
12 extern "C" void CApplicationInit(void);
13 extern "C" void CApplicationDepositData(char *data);
14
15 #define TIME_INTERVAL 500
16 #ifndef WIN32
17 #include <sys/time.h>
18 #include <unistd.h>
19 #endif
20
21 main::main(CkArgMsg *m)
22
23   int arg_index = 1;
24   mainhandle=thishandle;
25   PartialBoard *pMsg = new  PartialBoard ;
26
27   if(m->argc<3)
28     CmiAbort("Usage: pgm N grain\n");
29   while ( m->argv[arg_index][0] == '+' )
30     arg_index++;
31   N = atoi(m->argv[arg_index]);
32   arg_index++;
33   grain = atoi(m->argv[arg_index]);
34   pMsg->nextRow = 0;
35   CProxy_queens::ckNew(pMsg);
36   t0 = CkTimer();
37   counterGroup = counterInit();
38   CkStartQD(CkIndex_main::Quiescence1((DUMMYMSG *)0), &mainhandle);
39 }
40
41 void main::Quiescence1(DUMMYMSG *msg) 
42
43   int numSolutions = CProxy_counter(counterGroup).ckLocalBranch()->getTotalCount();
44   CkPrintf("There are %d Solutions to %d queens. Finish time=%f\n",
45           numSolutions, N, CkTimer()-t0);
46   CkExit();
47 }
48
49 queens::queens(PartialBoard *m)
50
51   int col,i, row;
52   PartialBoard *newMsg;
53
54   row = m->nextRow;  
55   if (row == N) 
56     solutionFound(m->Queens);
57   else if ( (N-row) < grain) 
58     seqQueens(m->Queens, row); 
59   else
60   {
61     for (col = 0; col<N; col++) 
62       if (consistent(m->Queens, row, col))
63       {
64         newMsg = new  PartialBoard;
65         newMsg->nextRow = row + 1;
66         for (i=0; i<N; i++)
67           newMsg->Queens[i] = m->Queens[i];
68         newMsg->Queens[row] = col;
69         CProxy_queens::ckNew(newMsg);  
70       }
71   }
72   delete m;
73   delete this;
74 }
75
76
77 void queens::solutionFound(int kqueens[])
78
79   int row;
80   char buf[800], tmp[800];
81   CProxy_counter(counterGroup).ckLocalBranch()->increment();
82   buf[0] = '\0';
83   sprintf(tmp,"%d:", CkMyPe());
84   strcat(buf,tmp);
85   for (row=0; row<N; row++)
86   { 
87     sprintf(tmp, "(%d,%d) ", row, kqueens[row]);
88     strcat(buf, tmp);
89   }
90   //  CkPrintf("%s\n", buf);
91 }
92
93 void queens::seqQueens(int kqueens[], int nextRow)
94
95   int col;
96
97   if (nextRow == N) 
98   { solutionFound(kqueens);
99     return; 
100   }
101   for (col = 0; col<N; col++) 
102     if (consistent(kqueens, nextRow, col))
103     {
104       kqueens[nextRow] = col;
105       seqQueens(kqueens, nextRow+1);
106     }
107 }
108
109 int queens::consistent(int kqueens[], int lastRow, int col)
110
111   /* check if the new queen is safe from each of the */
112   /* previously placed queens */
113   int x,y;
114
115   for (x=0; x<lastRow; x++)
116   { 
117     y = kqueens[x];
118     if ((y==col)  || ((lastRow-x) == (col-y)) || ((lastRow-x) == (y-col)) ) {
119       return(0);
120     }
121   }
122   return(1);
123 }