HOG2
NQueens.cpp
Go to the documentation of this file.
1 //
2 // NQueens.cpp
3 // hog2 glut
4 //
5 // Created by Nathan Sturtevant on 9/18/11.
6 // Copyright 2011 University of Denver. All rights reserved.
7 //
8 
9 #include "NQueens.h"
10 #include "GLUtil.h"
11 
12 void NQueens::GetSuccessors(const NQueenState &nodeID, std::vector<NQueenState> &neighbors) const
13 {
14 
15 }
16 
17 void NQueens::GetActions(const NQueenState &nodeID, std::vector<NQueenAction> &actions) const
18 {
19  actions.resize(0);
20  for (unsigned int x = 0; x < nodeID.locs.size(); x++)
21  {
22  for (unsigned int y = 0; y < nodeID.locs.size(); y++)
23  {
24  if (nodeID.locs[x] == y)
25  continue;
26 
27  NQueenAction a;
28  a.loc = x;
29  a.value = y;
30  actions.push_back(a);
31  }
32  }
33 }
34 
35 NQueenAction NQueens::GetAction(const NQueenState &s1, const NQueenState &s2) const
36 {
37  assert(false);
38  NQueenAction a;
39  return a;
40 }
41 
42 void NQueens::ApplyAction(NQueenState &s, NQueenAction a) const
43 {
44  s.locs[a.loc] = a.value;
45 }
46 
47 void NQueens::GetNextState(const NQueenState &s, NQueenAction a, NQueenState &s2) const
48 {
49  s2 = s;
50  ApplyAction(s2, a);
51 }
52 
54 bool NQueens::GoalTest(const NQueenState &node) const
55 {
56  for (int x = 0; x < node.locs.size(); x++)
57  {
58  int up = node.locs[x];
59  if (up == -1) return false;
60  int down = up;
61  int middle = up;
62 
63  for (int y = 1; y < node.locs.size(); y++)
64  {
65  up -= 1;
66  down += 1;
67 
68  if ((x-y < 0) && (x+y >= node.locs.size()))
69  break;
70 
71  if ((x+y < node.locs.size()) &&
72  ((node.locs[x+y] == up) ||
73  (node.locs[x+y] == down) ||
74  (node.locs[x+y] == middle)))
75  {
76  return false;
77  }
78  if ((x-y >= 0) &&
79  ((node.locs[x-y] == up) ||
80  (node.locs[x-y] == down) ||
81  (node.locs[x-y] == middle)))
82  {
83  return false;
84  }
85  }
86  }
87  return true;
88 }
89 int NQueens::NumCollisions(const NQueenState &node, int row, int column) const
90 {
91  if (row > node.locs.size())
92  return -1;
93  int count = 0;
94  int x = row;
95  {
96  int up = column;
97  if (up == -1)
98  {
99  // ill formed state
100  return -1;
101  }
102  int down = up;
103  int middle = up;
104 
105  for (int y = 1; y < node.locs.size(); y++)
106  {
107  up -= 1;
108  down += 1;
109 
110  if ((x-y < 0) && (x+y >= node.locs.size()))
111  break;
112 
113  if (x+y < node.locs.size())
114  {
115  if (node.locs[x+y] == up) count++;
116  if (node.locs[x+y] == down) count++;
117  if (node.locs[x+y] == middle) count++;
118  }
119  if (x-y >= 0)
120  {
121  if (node.locs[x-y] == up) count++;
122  if (node.locs[x-y] == down) count++;
123  if (node.locs[x-y] == middle) count++;
124  }
125  }
126  }
127  return count;
128 }
129 
130 
131 int NQueens::NumCollisions(const NQueenState &node, int row) const
132 {
133  if (row > node.locs.size())
134  return -1;
135  int count = 0;
136  int x = row;
137  {
138  int up = node.locs[x];
139  if (up == -1)
140  {
141  // ill formed state
142  return -1;
143  }
144  int down = up;
145  int middle = up;
146 
147  for (int y = 1; y < node.locs.size(); y++)
148  {
149  up -= 1;
150  down += 1;
151 
152  if ((x-y < 0) && (x+y >= node.locs.size()))
153  break;
154 
155  if (x+y < node.locs.size())
156  {
157  if (node.locs[x+y] == up) count++;
158  if (node.locs[x+y] == down) count++;
159  if (node.locs[x+y] == middle) count++;
160  }
161  if (x-y >= 0)
162  {
163  if (node.locs[x-y] == up) count++;
164  if (node.locs[x-y] == down) count++;
165  if (node.locs[x-y] == middle) count++;
166  }
167  }
168  }
169  return count;
170 }
171 
172 int NQueens::NumCollisions(const NQueenState &node) const
173 {
174  int count = 0;
175  for (int x = 0; x < node.locs.size(); x++)
176  {
177  int up = node.locs[x];
178  if (up == -1)
179  {
180  // ill formed state
181  continue;
182  }
183  int down = up;
184  int middle = up;
185 
186  for (int y = 1; y < node.locs.size(); y++)
187  {
188  up -= 1;
189  down += 1;
190 
191  if ((x-y < 0) && (x+y >= node.locs.size()))
192  break;
193 
194  if (x+y < node.locs.size())
195  {
196  if (node.locs[x+y] == up) count++;
197  if (node.locs[x+y] == down) count++;
198  if (node.locs[x+y] == middle) count++;
199  }
200  if (x-y >= 0)
201  {
202  if (node.locs[x-y] == up) count++;
203  if (node.locs[x-y] == down) count++;
204  if (node.locs[x-y] == middle) count++;
205  }
206  }
207  }
208  return count;
209 }
210 
211 void NQueens::OpenGLDraw() const
212 {
213  // no basic environment to draw
214 }
215 
216 void NQueens::OpenGLDrawBackground(float r, float g, float b)
217 {
218  glBegin(GL_QUADS);
219  glColor3f(r, g, b);
220  glVertex3d(-1.0, 1.0, 0.01);
221  glVertex3d(-1.0, -1.0, 0.01);
222  glVertex3d( 1.0, -1.0, 0.01);
223  glVertex3d( 1.0, 1.0, 0.01);
224  glEnd();
225 }
226 
227 void NQueens::OpenGLDrawBackground(const NQueenState&s, float r, float g, float b, int firstRow, int lastRow)
228 {
229  double fract = s.locs.size();
230  fract = 2.0/fract;
231  glColor3f(r, g, b);
232  glBegin(GL_QUADS);
233  glVertex3d(-1.0+firstRow*fract, 1, 0);
234  glVertex3d(-1.0+firstRow*fract, -1, 0);
235  glVertex3d(-1.0+lastRow*fract, -1, 0);
236  glVertex3d(-1.0+lastRow*fract, 1, 0);
237  glEnd();
238 }
239 
240 
241 void NQueens::OpenGLDraw(const NQueenState&s) const
242 {
243  double fract = s.locs.size();
244  fract = 2.0/fract;
245  glBegin(GL_LINES);
246  glColor3f(1.0, 1.0, 1.0);
247  for (unsigned int x = 0; x <= s.locs.size(); x++)
248  {
249  glVertex3d(-1.0+x*fract, -1, 0);
250  glVertex3d(-1.0+x*fract, 1, 0);
251 
252  glVertex3d(-1, -1.0+x*fract, 0);
253  glVertex3d( 1, -1.0+x*fract, 0);
254  }
255  glEnd();
256  glBegin(GL_QUADS);
257  for (unsigned int x = 0; x < s.locs.size(); x++)
258  {
259  int count;
260  if ((count = NumCollisions(s, x)) == 0)
261  glColor3f(0.2, 1.0, 0.2);
262  else
263  glColor3f(1.0, 0.1, 0.1);
264  glVertex3d(-1.0+x*fract, -1.0+s.locs[x]*fract, 0.0);
265  glVertex3d(-1.0+x*fract, -1.0+(1+s.locs[x])*fract, 0.0);
266  glVertex3d(-1.0+(x+1)*fract, -1.0+(1+s.locs[x])*fract, 0.0);
267  glVertex3d(-1.0+(x+1)*fract, -1.0+s.locs[x]*fract, 0.0);
268  }
269  glEnd();
270 
271  if (0) // draw lines
272  {
273  glColor3f(1.0, 0, 0);
274  glLineWidth(3.0);
275  glBegin(GL_LINES);
276  for (int x = 0; x < s.locs.size(); x++)
277  {
278  int up = s.locs[x];
279  if (up == -1) continue;
280  int down = up;
281  for (int y = 1; y < s.locs.size(); y++)
282  {
283  up -= 1;
284  down += 1;
285  if (y == 1)
286  continue;
287 
288  // root location
289  glVertex3d(-1.0+x*fract+fract*0.5+(y-1)*fract, -1.0+s.locs[x]*fract+fract*0.5, 0.0);
290  // offset: right
291  glVertex3d(-1.0+x*fract+fract*0.5+y*fract, -1.0+s.locs[x]*fract+fract*0.5, 0.0);
292 
293  // root location
294  glVertex3d(-1.0+x*fract+fract*0.5-(y-1)*fract, -1.0+s.locs[x]*fract+fract*0.5, 0.0);
295  // offset: left
296  glVertex3d(-1.0+x*fract+fract*0.5-y*fract, -1.0+s.locs[x]*fract+fract*0.5, 0.0);
297 
298  // root location
299  glVertex3d(-1.0+x*fract+fract*0.5-(y-1)*fract, -1.0+(up+1)*fract+fract*0.5, 0.0);
300  // offset: up-left
301  glVertex3d(-1.0+x*fract+fract*0.5-y*fract, -1.0+up*fract+fract*0.5, 0.0);
302 
303  // root location
304  glVertex3d(-1.0+x*fract+fract*0.5-(y-1)*fract, -1.0+(down-1)*fract+fract*0.5, 0.0);
305  // offset: down-left
306  glVertex3d(-1.0+x*fract+fract*0.5-y*fract, -1.0+down*fract+fract*0.5, 0.0);
307 
308  // root location
309  glVertex3d(-1.0+x*fract+fract*0.5+(y-1)*fract, -1.0+(up+1)*fract+fract*0.5, 0.0);
310  // offset: up-right
311  glVertex3d(-1.0+x*fract+fract*0.5+y*fract, -1.0+up*fract+fract*0.5, 0.0);
312 
313  // root location
314  glVertex3d(-1.0+x*fract+fract*0.5+(y-1)*fract, -1.0+(down-1)*fract+fract*0.5, 0.0);
315  // offset: down-right
316  glVertex3d(-1.0+x*fract+fract*0.5+y*fract, -1.0+down*fract+fract*0.5, 0.0);
317 
318  }
319  }
320  glEnd();
321  }
322  glLineWidth(1.0);
323 }
324 
325 void NQueens::OpenGLDrawConflicts(const NQueenState&s) const
326 {
327  for (unsigned int x = 0; x < s.locs.size(); x++)
328  {
329  int count = NumCollisions(s, x);
330  GLLabelState(s, x, s.locs[x], count);
331  if (count != 0)
332  {
333  for (int y = 0; y < s.locs.size(); y++)
334  {
335  if (y != s.locs[x])
336  GLLabelState(s, x, y, NumCollisions(s, x, y));
337  }
338  }
339  }
340 }
341 
342 
343 void NQueens::GLLabelState(const NQueenState &s, int x, int y, int number) const
344 {
345  glDisable(GL_LIGHTING);
346  glEnable(GL_LINE_SMOOTH);
347  glDisable(GL_DEPTH_TEST);
348  glLineWidth(3.0);
349 
350  int w = (int)s.locs.size();
351  int h = (int)s.locs.size();
352  glPushMatrix();
353  glColor3f(1.0, 1.0, 1.0);
354  glTranslatef(x*2.0/w-1.0, (1+y)*2.0/h-1.0, -0.001);
355  glScalef(1.0/(w*120.0), 1.0/(h*120.0), 1);
356  glRotatef(180, 0.0, 0.0, 1.0);
357  glRotatef(180, 0.0, 1.0, 0.0);
358  //glTranslatef((float)x/width-0.5, (float)y/height-0.5, 0);
359  //if (number > 9)
360  // glutStrokeCharacter(GLUT_STROKE_ROMAN, '0'+(((number)/10)%10));
361  //if (number > 0)
362  // glutStrokeCharacter(GLUT_STROKE_ROMAN, '0'+((number)%10));
363  //glTranslatef(-x/width+0.5, -y/height+0.5, 0);
364  glPopMatrix();
365 
366 
367  glEnable(GL_DEPTH_TEST);
368  glEnable(GL_LIGHTING);
369  glDisable(GL_LINE_SMOOTH);
370  glLineWidth(1.0);
371 }
372 
374 void NQueens::OpenGLDraw(const NQueenState&, const NQueenState&, float) const
375 {
376 
377 }
378 
379 void NQueens::OpenGLDraw(const NQueenState&, const NQueenAction&) const
380 {
381  return;
382 }
NQueens.h
NQueens::GetSuccessors
virtual void GetSuccessors(const NQueenState &nodeID, std::vector< NQueenState > &neighbors) const
Definition: NQueens.cpp:12
NQueenAction
Definition: NQueens.h:40
NQueens::ApplyAction
virtual void ApplyAction(NQueenState &s, NQueenAction a) const
Definition: NQueens.cpp:42
NQueenState
Definition: NQueens.h:16
NQueens::OpenGLDrawBackground
void OpenGLDrawBackground(float r, float g, float b)
Definition: NQueens.cpp:216
NQueens::GoalTest
virtual bool GoalTest(const NQueenState &node, const NQueenState &goal) const
Definition: NQueens.h:77
GLUtil.h
NQueens::OpenGLDraw
virtual void OpenGLDraw() const
Definition: NQueens.cpp:211
NQueenState::locs
std::vector< int > locs
Definition: NQueens.h:25
NQueens::GetNextState
virtual void GetNextState(const NQueenState &, NQueenAction, NQueenState &) const
Definition: NQueens.cpp:47
NQueens::GetActions
virtual void GetActions(const NQueenState &nodeID, std::vector< NQueenAction > &actions) const
Definition: NQueens.cpp:17
NQueens::NumCollisions
int NumCollisions(const NQueenState &node) const
Definition: NQueens.cpp:172
NQueenAction::value
int value
Definition: NQueens.h:43
NQueens::GLLabelState
void GLLabelState(const NQueenState &s, int x, int y, int number) const
Definition: NQueens.cpp:343
NQueens::OpenGLDrawConflicts
void OpenGLDrawConflicts(const NQueenState &s) const
Definition: NQueens.cpp:325
NQueens::GetAction
virtual NQueenAction GetAction(const NQueenState &s1, const NQueenState &s2) const
Definition: NQueens.cpp:35
NQueenAction::loc
int loc
Definition: NQueens.h:43
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
Generated by   doxygen 1.8.17