2 * queens - solves n queens problem, displays
3 * i make no claims that this is an optimal solution to the problem,
7 * version 1.0 - May 10, 2002
9 * Copyright (C) 2002 Blair Tennessy (tennessy@cs.ubc.ca)
11 * Permission to use, copy, modify, distribute, and sell this software and its
12 * documentation for any purpose is hereby granted without fee, provided that
13 * the above copyright notice appear in all copies and that both that
14 * copyright notice and this permission notice appear in supporting
15 * documentation. No representations are made about the suitability of this
16 * software for any purpose. It is provided "as is" without express or
21 #define DEFAULTS "*delay: 20000 \n" \
22 "*showFPS: False \n" \
23 "*wireframe: False \n" \
25 # define refresh_queens 0
26 # include "xlockmore.h"
34 #include "gltrackball.h"
37 #define countof(x) (sizeof((x))/sizeof((*x)))
39 static XrmOptionDescRec opts[] = {
40 {"+rotate", ".queens.rotate", XrmoptionNoArg, "false" },
41 {"-rotate", ".queens.rotate", XrmoptionNoArg, "true" },
42 {"+flat", ".queens.flat", XrmoptionNoArg, "false" },
43 {"-flat", ".queens.flat", XrmoptionNoArg, "true" },
46 static int rotate, wire, clearbits, flat;
48 static argtype vars[] = {
49 {&rotate, "rotate", "Rotate", "True", t_Bool},
50 {&flat, "flat", "Flat", "False", t_Bool},
53 ENTRYPOINT ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
56 ModStruct queens_description =
57 {"queens", "init_queens", "draw_queens", "release_queens",
58 "draw_queens", "init_queens", NULL, &queens_opts,
59 1000, 1, 2, 1, 4, 1.0, "",
71 GLXContext *glx_context;
73 trackball_state *trackball;
77 int board[MAXBOARD][MAXBOARD];
78 int steps, colorset, BOARDSIZE;
84 static Queenscreen *qss = NULL;
86 /* definition of white/black colors */
87 static const GLfloat colors[COLORSETS][2][3] =
89 {{0.43, 0.54, 0.76}, {0.8, 0.8, 0.8}},
90 {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
91 {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
92 {{0.15, 0.77, 0.54}, {0.5, 0.5, 0.5}},
93 {{0.9, 0.45, 0.0}, {0.5, 0.5, 0.5}},
97 queens_handle_event (ModeInfo *mi, XEvent *event)
99 Queenscreen *qs = &qss[MI_SCREEN(mi)];
101 if (event->xany.type == ButtonPress &&
102 event->xbutton.button == Button1)
104 qs->button_down_p = True;
105 gltrackball_start (qs->trackball,
106 event->xbutton.x, event->xbutton.y,
107 MI_WIDTH (mi), MI_HEIGHT (mi));
110 else if (event->xany.type == ButtonRelease &&
111 event->xbutton.button == Button1)
113 qs->button_down_p = False;
116 else if (event->xany.type == ButtonPress &&
117 (event->xbutton.button == Button4 ||
118 event->xbutton.button == Button5 ||
119 event->xbutton.button == Button6 ||
120 event->xbutton.button == Button7))
122 gltrackball_mousewheel (qs->trackball, event->xbutton.button, 5,
123 !event->xbutton.state);
126 else if (event->xany.type == MotionNotify &&
129 gltrackball_track (qs->trackball,
130 event->xmotion.x, event->xmotion.y,
131 MI_WIDTH (mi), MI_HEIGHT (mi));
140 /* returns true if placing a queen on column c causes a conflict */
141 static int conflictsCols(Queenscreen *qs, int c)
145 for(i = 0; i < qs->BOARDSIZE; ++i)
152 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
153 static int conflictsDiag(Queenscreen *qs, int r, int c)
158 int n = r < c ? r : c;
159 for(i = 0; i < qs->BOARDSIZE-abs(r-c); ++i)
160 if(qs->board[r-n+i][c-n+i])
164 n = r < qs->BOARDSIZE - (c+1) ? r : qs->BOARDSIZE - (c+1);
165 for(i = 0; i < qs->BOARDSIZE-abs(qs->BOARDSIZE - (1+r+c)); ++i)
166 if(qs->board[r-n+i][c+n-i])
172 /* returns true if placing a queen at (r,c) causes a conflict */
173 static int conflicts(Queenscreen *qs, int r, int c)
175 return !conflictsCols(qs, c) ? conflictsDiag(qs, r, c) : 1;
179 static void blank(Queenscreen *qs)
183 for(i = 0; i < MAXBOARD; ++i)
184 for(j = 0; j < MAXBOARD; ++j)
185 qs->board[i][j] = NONE;
188 /* recursively determine solution */
189 static int findSolution(Queenscreen *qs, int row, int col)
191 if(row == qs->BOARDSIZE)
194 while(col < qs->BOARDSIZE) {
195 if(!conflicts(qs, row, col)) {
196 qs->board[row][col] = 1;
198 if(findSolution(qs, row+1, 0))
201 qs->board[row][col] = 0;
210 /** driver for finding solution */
211 static void go(Queenscreen *qs) { while(!findSolution(qs, 0, random()%qs->BOARDSIZE)); }
213 /* lighting variables */
214 static const GLfloat front_shininess[] = {60.0};
215 static const GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
216 static const GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
217 static const GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
219 /* configure lighting */
220 static void setup_lights(Queenscreen *qs)
223 /* setup twoside lighting */
224 glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
225 glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
226 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
227 glEnable(GL_LIGHTING);
230 /* setup material properties */
231 glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
232 glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
234 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
237 #define checkImageWidth 8
238 #define checkImageHeight 8
239 /*static GLubyte checkImage[checkImageWidth][checkImageHeight][3];*/
241 /* return alpha value for fading */
242 static GLfloat findAlpha(Queenscreen *qs)
244 return qs->steps < 128 ? qs->steps/128.0 : qs->steps < 1024-128 ?1.0:(1024-qs->steps)/128.0;
248 static int drawPieces(Queenscreen *qs)
253 for(i = 0; i < qs->BOARDSIZE; ++i) {
254 for(j = 0; j < qs->BOARDSIZE; ++j) {
255 if(qs->board[i][j]) {
256 glColor3fv(colors[qs->colorset][i%2]);
258 polys += qs->queen_polys;
261 glTranslatef(1.0, 0.0, 0.0);
264 glTranslatef(-1.0*qs->BOARDSIZE, 0.0, 1.0);
269 /** reflectionboard */
270 static int draw_reflections(Queenscreen *qs)
275 glEnable(GL_STENCIL_TEST);
276 glStencilFunc(GL_ALWAYS, 1, 1);
277 glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
278 glColorMask(0,0,0,0);
279 glDisable(GL_CULL_FACE);
281 glDisable(GL_DEPTH_TEST);
284 /* only draw white squares */
285 for(i = 0; i < qs->BOARDSIZE; ++i) {
286 for(j = (qs->BOARDSIZE+i) % 2; j < qs->BOARDSIZE; j += 2) {
287 glVertex3f(i, 0.0, j + 1.0);
288 glVertex3f(i + 1.0, 0.0, j + 1.0);
289 glVertex3f(i + 1.0, 0.0, j);
290 glVertex3f(i, 0.0, j);
295 glEnable(GL_DEPTH_TEST);
297 glColorMask(1, 1, 1, 1);
298 glStencilFunc(GL_EQUAL, 1, 1);
299 glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
302 glScalef(1.0, -1.0, 1.0);
303 glTranslatef(0.5, 0.001, 0.5);
304 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
305 polys += drawPieces(qs);
307 glDisable(GL_STENCIL_TEST);
310 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
312 glEnable(GL_CULL_FACE);
314 glColorMask(1,1,1,1);
319 static int drawBoard(Queenscreen *qs)
326 for(i = 0; i < qs->BOARDSIZE; ++i)
327 for(j = 0; j < qs->BOARDSIZE; ++j) {
328 int par = (i-j+qs->BOARDSIZE)%2;
329 glColor4f(colors[qs->colorset][par][0],
330 colors[qs->colorset][par][1],
331 colors[qs->colorset][par][2],
333 glNormal3f(0.0, 1.0, 0.0);
334 glVertex3f(i, 0.0, j + 1.0);
335 glVertex3f(i + 1.0, 0.0, j + 1.0);
336 glVertex3f(i + 1.0, 0.0, j);
337 glVertex3f(i, 0.0, j);
345 static int display(Queenscreen *qs)
350 glMatrixMode(GL_MODELVIEW);
353 /* setup light attenuation */
354 glEnable(GL_COLOR_MATERIAL);
355 glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
356 glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
358 /** setup perspective */
359 glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
360 glRotatef(30.0, 1.0, 0.0, 0.0);
361 gltrackball_rotate (qs->trackball);
362 glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
363 glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
365 /* find light positions */
366 qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
367 qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
368 qs->position[1] = 6.0;
371 glEnable(GL_LIGHTING);
372 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
376 /* draw reflections */
378 polys += draw_reflections(qs);
381 polys += drawBoard(qs);
385 glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
387 glTranslatef(0.5, 0.0, 0.5);
388 polys += drawPieces(qs);
391 if(!qs->button_down_p)
394 /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
395 if(++qs->steps == 1024) {
398 qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
399 qs->colorset = (qs->colorset+1)%COLORSETS;
405 static const GLfloat spidermodel[][3] =
425 #define EPSILON 0.001
427 /** draws cylindermodel */
428 static int draw_model(int chunks, const GLfloat model[][3], int r)
432 GLUquadricObj *quadric = gluNewQuadric();
434 glRotatef(-90.0, 1.0, 0.0, 0.0);
436 for(i = 0; i < chunks; ++i) {
437 if(model[i][0] > EPSILON || model[i][1] > EPSILON) {
438 gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
441 glTranslatef(0.0, 0.0, model[i][2]);
448 ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height)
450 GLfloat h = (GLfloat) height / (GLfloat) width;
451 glViewport(0,0, width, height);
452 glMatrixMode(GL_PROJECTION);
454 gluPerspective(45, 1/h, 2.0, 30.0);
455 glMatrixMode(GL_MODELVIEW);
458 ENTRYPOINT void init_queens(ModeInfo *mi)
460 int screen = MI_SCREEN(mi);
462 wire = MI_IS_WIREFRAME(mi);
465 !(qss = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
469 qs->window = MI_WINDOW(mi);
470 qs->trackball = gltrackball_init ();
472 qs->BOARDSIZE = 8; /* 8 cuz its classic */
474 if((qs->glx_context = init_GL(mi)))
475 reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
479 glClearColor(0.0, 0.0, 0.0, 0.0);
480 glNewList(QUEEN, GL_COMPILE);
481 qs->queen_polys = draw_model(countof(spidermodel), spidermodel, 24);
485 glShadeModel(GL_FLAT);
487 clearbits = GL_COLOR_BUFFER_BIT;
489 glColorMaterial(GL_FRONT, GL_DIFFUSE);
490 glEnable(GL_COLOR_MATERIAL);
494 glEnable(GL_DEPTH_TEST);
495 clearbits |= GL_DEPTH_BUFFER_BIT;
496 clearbits |= GL_STENCIL_BUFFER_BIT;
497 glEnable(GL_CULL_FACE);
501 glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
503 /* find a solution */
507 ENTRYPOINT void draw_queens(ModeInfo *mi)
509 Queenscreen *qs = &qss[MI_SCREEN(mi)];
510 Window w = MI_WINDOW(mi);
511 Display *disp = MI_DISPLAY(mi);
516 glXMakeCurrent(disp, w, *(qs->glx_context));
518 mi->polygon_count = display(qs);
520 if(mi->fps_p) do_fps(mi);
522 glXSwapBuffers(disp, w);
525 ENTRYPOINT void release_queens(ModeInfo *mi)
534 XSCREENSAVER_MODULE ("Queens", queens)