1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include "thread_c.h"
static int repeat = 10;
static int size = 14;
static unsigned int cutOff = 7;
struct board {
unsigned int queens, limit, left, down, right, kill;
};
static struct board
init(unsigned int width)
{
struct board b;
b.queens = width;
b.limit = 1 << width;
b.left = 0;
b.down = 0;
b.right = 0;
b.kill = 0;
return b;
}
static struct board *
put(const struct board *b, unsigned int bit)
{
struct board *r = malloc(sizeof(struct board));;
r->queens = b->queens - 1;
r->limit = b->limit;
r->left = (b->left | bit) >> 1;
r->down = b->down | bit;
r->right = (b->right | bit) << 1;
r->kill = r->left | r->down | r->right;
return r;
}
static int solve(const struct board *);
static int
ssum(const struct board *board, unsigned int bit)
{
struct board *b;
int sum = 0;
while (bit < board->limit) {
if ((board->kill & bit) == 0) {
b = put(board, bit);
sum += solve(b);
free(b);
}
bit <<= 1;
}
return sum;
}
static void *
psum_fn(void *arg)
{
const struct board *board = arg;
int result = solve(board);
free((void*)board);
return RET(result);
}
static int
psum(const struct board *board, unsigned int bit)
{
struct board *b;
thread_t t;
int n;
while (bit < board->limit) {
if ((board->kill & bit) == 0) {
b = put(board, bit);
t = create(psum_fn, b);
n = psum(board, bit << 1);
return n + GET(join(t));
}
bit <<= 1;
}
return 0;
}
static int
solve(const struct board *board)
{
if (board->queens == 0)
return 1;
else if (board->queens <= cutOff)
return ssum(board, 1);
else
return psum(board, 1);
}
static int
doit()
{
const struct board b = init(size);
return solve(&b);
}
static void
rep(int n)
{
struct timeval t1, t2;
double d1, d2;
int r;
while (n > 0) {
gettimeofday(&t1, NULL);
r = doit();
gettimeofday(&t2, NULL);
d1 = t1.tv_sec + (double)t1.tv_usec / 1000000;
d2 = t2.tv_sec + (double)t2.tv_usec / 1000000;
printf(" - {result: %d, time: %.6f}\n", r, d2 - d1);
n--;
}
}
int
main(int argc, char **argv)
{
if (argc > 1) repeat = atoi(argv[1]);
if (argc > 2) size = atoi(argv[2]);
if (argc > 3) cutOff = atoi(argv[3]);
printf(" bench: nqueen_c_%s\n size: %d\n cutoff: %d\n results:\n",
threadtype, size, cutOff);
rep(repeat);
return 0;
}
|
