Salvador Abreu / PaCCS

Blame view

bench/queens2.c 3.02 KB
Edit Raw Normal View History
965dadaa   Salvador Abreu   initial commit fr... 
1
2
3
 
/* solves two unconnected queens problems */

#include <stdio.h>
eef94371   Vasco Pedro   Update to PaCCS v... 
4
5
 
#include <fcntl.h>
#include <errno.h>
965dadaa   Salvador Abreu   initial commit fr... 
6
7
8
 

#include "fdc_int.h"
eef94371   Vasco Pedro   Update to PaCCS v... 
9
 
#define NMAX 200		// maximum number of queens
965dadaa   Salvador Abreu   initial commit fr... 
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
 

static int N1 = 11, N2 = 11;	// actual number of queens

void init_queens(fd_int *queens, int N)
{
#define queens (queens + BASE)
  static int BASE = 0;
  int i, j;

/*
  FORWARD_CHECKING REBENTA(VA) (N == 6)

  queens[0] = fd_new(2, 5);
  _fd_val_del_val(5, queens[0]->domain);
  queens[N - 1] = fd_new(6, 6);
*/

  //queens[0] = fd_new(2, 2);
  //queens[1] = fd_new(5, 5);
  //queens[2] = fd_new(3, 3);

  // N == 20
  //queens[0] = fd_new(3, 3);
  //queens[1] = fd_new(12, 12);
  //queens[2] = fd_new(9, 9);
  //queens[3] = fd_new(17, 17);
  //queens[4] = fd_new(14, 14);
  //queens[5] = fd_new(5, 5);
  //queens[6] = fd_new(15, 15);

  for (i = 0; i < N; ++i)
#if 0
    if (i == 0)
      queens[i] = fd_new(1, 1);
    else if (i == 99)
      queens[i] = fd_new(2, 2);
    else
#endif
      queens[i] = fd_new(1, N);

  //queens[N - 1] = fd_new(6, 6);

#if 01
  fd_fake_all_different(queens, N);
#elif 01
  fd_all_different(queens, N);
#else
  for (i = 0; i < N; ++i)
    fd_exactly_one(queens, N, i + 1);
#endif

  for (i = 0; i < N; ++i)
    for (j = i + 1; j < N; ++j)
      fd_minus_ne(queens[i], queens[j], i - j);

  for (i = 0; i < N; ++i)
    for (j = i + 1; j < N; ++j)
      fd_minus_ne(queens[i], queens[j], j - i);

  BASE += N;
#undef queens
}

int main(int argc, char *argv[])
{
  fd_int queens[2 * NMAX];
  int solutions = 0, one_solution = 1;
  int i, j;
  int seed;
  int dev_random;
965dadaa   Salvador Abreu   initial commit fr... 
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 

  fd_init(&argc, &argv);

  for (i = 1; i < argc; ++i)
    if (!strcmp(argv[i], "--all"))
      one_solution = 0;
    else
      {
	N1 = atoi(argv[i]);

	if (i + 1 < argc)
	  N2 = atoi(argv[++i]);
      }

#ifdef LOCAL_SEARCH
eef94371   Vasco Pedro   Update to PaCCS v... 
95
 
#if 01
965dadaa   Salvador Abreu   initial commit fr... 
96
97
98
99
100
101
 
  seed = time(0);
  seed = 1206987119;
  //seed = 1207917731; // N = 6, best improvement termina
  //seed = 0;
#else
    if ((dev_random = open("/dev/urandom", O_RDONLY)) == -1)
eef94371   Vasco Pedro   Update to PaCCS v... 
102
103
104
105
 
    _fd_fatal("/dev/urandom: %s\n", strerror(errno));

  read(dev_random, &seed, sizeof(seed));
#endif
965dadaa   Salvador Abreu   initial commit fr... 
106
107
108
109
110
 

  srandom(seed);
  _fd_debug("seed = %u\n", seed);
#endif
eef94371   Vasco Pedro   Update to PaCCS v... 
111
 
  init_queens(queens, N1);
965dadaa   Salvador Abreu   initial commit fr... 
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
  init_queens(queens, N2);

  while (fd_solve() == FD_OK)
    {
      printf("solution %d:\n", ++solutions);

      printf("problem 1\n");

#if 01
      for (i = 0; i < N1; ++i)
	if (!fd_var_single(queens[i], NULL))
	  _fd_fatal("solution contains non-singleton variable");
#endif
eef94371   Vasco Pedro   Update to PaCCS v... 
126
 
      for (i = 0; i < N1; ++i)
965dadaa   Salvador Abreu   initial commit fr... 
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
	{
	  fd_print(queens[i]);
	  putchar(' ');
	}
      putchar('\n');

      printf("problem 2\n");

#if 01
      for (i = N1; i < N1 + N2; ++i)
	if (!fd_var_single(queens[i], NULL))
	  _fd_fatal("solution contains non-singleton variable");
#endif
eef94371   Vasco Pedro   Update to PaCCS v... 
141
 
      for (i = N1; i < N1 + N2; ++i)
965dadaa   Salvador Abreu   initial commit fr... 
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
	{
	  fd_print(queens[i]);
	  putchar(' ');
	}
      putchar('\n');

#if !(defined(LOCAL_SEARCH) || defined(DISTRIBUTED_SOLVER))
      if (one_solution)
#endif
	break;
    }

  if (solutions)
    printf("%d solutions found\n", solutions);
  else
    printf("inconsistent CSP\n");

  fd_end();

  return !solutions;
}