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"
35 # include <X11/Xlib.h>
42 #endif /* HAVE_JWZGLES */
46 #include "gltrackball.h"
47 #include "chessmodels.h"
50 #define countof(x) (sizeof((x))/sizeof((*x)))
52 static XrmOptionDescRec opts[] = {
53 {"+rotate", ".queens.rotate", XrmoptionNoArg, "false" },
54 {"-rotate", ".queens.rotate", XrmoptionNoArg, "true" },
55 {"+flat", ".queens.flat", XrmoptionNoArg, "false" },
56 {"-flat", ".queens.flat", XrmoptionNoArg, "true" },
59 static int rotate, wire, clearbits, flat;
61 static argtype vars[] = {
62 {&rotate, "rotate", "Rotate", "True", t_Bool},
63 {&flat, "flat", "Flat", "False", t_Bool},
66 ENTRYPOINT ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
69 ModStruct queens_description =
70 {"queens", "init_queens", "draw_queens", "release_queens",
71 "draw_queens", "init_queens", NULL, &queens_opts,
72 1000, 1, 2, 1, 4, 1.0, "",
83 GLXContext *glx_context;
85 trackball_state *trackball;
90 int board[MAXBOARD][MAXBOARD];
91 int steps, colorset, BOARDSIZE;
97 static Queenscreen *qss = NULL;
99 /* definition of white/black colors */
100 static const GLfloat colors[COLORSETS][2][3] =
102 {{0.43, 0.54, 0.76}, {0.8, 0.8, 0.8}},
103 {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
104 {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
105 {{0.15, 0.77, 0.54}, {0.5, 0.5, 0.5}},
106 {{0.9, 0.45, 0.0}, {0.5, 0.5, 0.5}},
110 queens_handle_event (ModeInfo *mi, XEvent *event)
112 Queenscreen *qs = &qss[MI_SCREEN(mi)];
114 if (event->xany.type == ButtonPress &&
115 event->xbutton.button == Button1)
117 qs->button_down_p = True;
118 gltrackball_start (qs->trackball,
119 event->xbutton.x, event->xbutton.y,
120 MI_WIDTH (mi), MI_HEIGHT (mi));
123 else if (event->xany.type == ButtonRelease &&
124 event->xbutton.button == Button1)
126 qs->button_down_p = False;
129 else if (event->xany.type == ButtonPress &&
130 (event->xbutton.button == Button4 ||
131 event->xbutton.button == Button5 ||
132 event->xbutton.button == Button6 ||
133 event->xbutton.button == Button7))
135 gltrackball_mousewheel (qs->trackball, event->xbutton.button, 5,
136 !event->xbutton.state);
139 else if (event->xany.type == MotionNotify &&
142 gltrackball_track (qs->trackball,
143 event->xmotion.x, event->xmotion.y,
144 MI_WIDTH (mi), MI_HEIGHT (mi));
153 /* returns true if placing a queen on column c causes a conflict */
154 static int conflictsCols(Queenscreen *qs, int c)
158 for(i = 0; i < qs->BOARDSIZE; ++i)
165 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
166 static int conflictsDiag(Queenscreen *qs, int r, int c)
171 int n = r < c ? r : c;
172 for(i = 0; i < qs->BOARDSIZE-abs(r-c); ++i)
173 if(qs->board[r-n+i][c-n+i])
177 n = r < qs->BOARDSIZE - (c+1) ? r : qs->BOARDSIZE - (c+1);
178 for(i = 0; i < qs->BOARDSIZE-abs(qs->BOARDSIZE - (1+r+c)); ++i)
179 if(qs->board[r-n+i][c+n-i])
185 /* returns true if placing a queen at (r,c) causes a conflict */
186 static int conflicts(Queenscreen *qs, int r, int c)
188 return !conflictsCols(qs, c) ? conflictsDiag(qs, r, c) : 1;
192 static void blank(Queenscreen *qs)
196 for(i = 0; i < MAXBOARD; ++i)
197 for(j = 0; j < MAXBOARD; ++j)
198 qs->board[i][j] = NONE;
201 /* recursively determine solution */
202 static int findSolution(Queenscreen *qs, int row, int col)
204 if(row == qs->BOARDSIZE)
207 while(col < qs->BOARDSIZE) {
208 if(!conflicts(qs, row, col)) {
209 qs->board[row][col] = 1;
211 if(findSolution(qs, row+1, 0))
214 qs->board[row][col] = 0;
223 /** driver for finding solution */
224 static void go(Queenscreen *qs) { while(!findSolution(qs, 0, random()%qs->BOARDSIZE)); }
226 /* lighting variables */
227 static const GLfloat front_shininess[] = {60.0};
228 static const GLfloat front_specular[] = {0.4, 0.4, 0.4, 1.0};
229 static const GLfloat ambient[] = {0.3, 0.3, 0.3, 1.0};
230 static const GLfloat diffuse[] = {0.8, 0.8, 0.8, 1.0};
232 /* configure lighting */
233 static void setup_lights(Queenscreen *qs)
236 /* setup twoside lighting */
237 glLightfv(GL_LIGHT0, GL_AMBIENT, ambient);
238 glLightfv(GL_LIGHT0, GL_DIFFUSE, diffuse);
239 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
240 glEnable(GL_LIGHTING);
243 /* setup material properties */
244 glMaterialfv(GL_FRONT_AND_BACK, GL_SHININESS, front_shininess);
245 glMaterialfv(GL_FRONT_AND_BACK, GL_SPECULAR, front_specular);
247 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
250 #define checkImageWidth 8
251 #define checkImageHeight 8
252 /*static GLubyte checkImage[checkImageWidth][checkImageHeight][3];*/
254 /* return alpha value for fading */
255 static GLfloat findAlpha(Queenscreen *qs)
257 return qs->steps < 128 ? qs->steps/128.0 : qs->steps < 1024-128 ?1.0:(1024-qs->steps)/128.0;
261 static int drawPieces(Queenscreen *qs)
266 for(i = 0; i < qs->BOARDSIZE; ++i) {
267 for(j = 0; j < qs->BOARDSIZE; ++j) {
268 if(qs->board[i][j]) {
269 glColor3fv(colors[qs->colorset][i%2]);
270 glCallList(qs->queen_list);
271 polys += qs->queen_polys;
274 glTranslatef(1.0, 0.0, 0.0);
277 glTranslatef(-1.0*qs->BOARDSIZE, 0.0, 1.0);
282 /** reflectionboard */
283 static int draw_reflections(Queenscreen *qs)
288 glEnable(GL_STENCIL_TEST);
289 glStencilFunc(GL_ALWAYS, 1, 1);
290 glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
291 glColorMask(0,0,0,0);
292 glDisable(GL_CULL_FACE);
294 glDisable(GL_DEPTH_TEST);
297 /* only draw white squares */
298 for(i = 0; i < qs->BOARDSIZE; ++i) {
299 for(j = (qs->BOARDSIZE+i) % 2; j < qs->BOARDSIZE; j += 2) {
300 glVertex3f(i, 0.0, j + 1.0);
301 glVertex3f(i + 1.0, 0.0, j + 1.0);
302 glVertex3f(i + 1.0, 0.0, j);
303 glVertex3f(i, 0.0, j);
308 glEnable(GL_DEPTH_TEST);
310 glColorMask(1, 1, 1, 1);
311 glStencilFunc(GL_EQUAL, 1, 1);
312 glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
315 glScalef(1.0, -1.0, 1.0);
316 glTranslatef(0.5, 0.001, 0.5);
317 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
318 polys += drawPieces(qs);
320 glDisable(GL_STENCIL_TEST);
323 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
325 glEnable(GL_CULL_FACE);
327 glColorMask(1,1,1,1);
332 static int drawBoard(Queenscreen *qs)
339 for(i = 0; i < qs->BOARDSIZE; ++i)
340 for(j = 0; j < qs->BOARDSIZE; ++j) {
341 int par = (i-j+qs->BOARDSIZE)%2;
342 glColor4f(colors[qs->colorset][par][0],
343 colors[qs->colorset][par][1],
344 colors[qs->colorset][par][2],
346 glNormal3f(0.0, 1.0, 0.0);
347 glVertex3f(i, 0.0, j + 1.0);
348 glVertex3f(i + 1.0, 0.0, j + 1.0);
349 glVertex3f(i + 1.0, 0.0, j);
350 glVertex3f(i, 0.0, j);
358 GLfloat w = qs->BOARDSIZE;
361 /* Give the board a slight lip. */
362 /* #### oops, normals are wrong here, but you can't tell */
364 glColor3f(0.3, 0.3, 0.3);
366 glVertex3f (0, 0, 0);
367 glVertex3f (0, -h, 0);
368 glVertex3f (0, -h, w);
369 glVertex3f (0, 0, w);
371 glVertex3f (0, 0, w);
372 glVertex3f (0, -h, w);
373 glVertex3f (w, -h, w);
374 glVertex3f (w, 0, w);
376 glVertex3f (w, 0, w);
377 glVertex3f (w, -h, w);
378 glVertex3f (w, -h, 0);
379 glVertex3f (w, 0, 0);
381 glVertex3f (w, 0, 0);
382 glVertex3f (w, -h, 0);
383 glVertex3f (0, -h, 0);
384 glVertex3f (0, 0, 0);
386 glVertex3f (0, -h, 0);
387 glVertex3f (w, -h, 0);
388 glVertex3f (w, -h, w);
389 glVertex3f (0, -h, w);
393 /* Fill in the underside of the board with an invisible black box
394 to hide the reflections that are not on tiles. Probably there's
395 a way to do this with stencils instead.
401 glTranslatef (off, 0, off);
402 glDisable(GL_LIGHTING);
405 glVertex3f (0, 0, 0);
406 glVertex3f (0, -h, 0);
407 glVertex3f (0, -h, w);
408 glVertex3f (0, 0, w);
410 glVertex3f (0, 0, w);
411 glVertex3f (0, -h, w);
412 glVertex3f (w, -h, w);
413 glVertex3f (w, 0, w);
415 glVertex3f (w, 0, w);
416 glVertex3f (w, -h, w);
417 glVertex3f (w, -h, 0);
418 glVertex3f (w, 0, 0);
420 glVertex3f (w, 0, 0);
421 glVertex3f (w, -h, 0);
422 glVertex3f (0, -h, 0);
423 glVertex3f (0, 0, 0);
425 glVertex3f (0, -h, 0);
426 glVertex3f (w, -h, 0);
427 glVertex3f (w, -h, w);
428 glVertex3f (0, -h, w);
433 glEnable(GL_LIGHTING);
439 static int display(Queenscreen *qs)
445 glMatrixMode(GL_MODELVIEW);
448 glRotatef(current_device_rotation(), 0, 0, 1);
450 /* setup light attenuation */
451 /* #### apparently this does nothing */
452 glEnable(GL_COLOR_MATERIAL);
453 glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha(qs)));
454 glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.06);
456 /** setup perspective */
457 glTranslatef(0.0, 0.0, -1.5*qs->BOARDSIZE);
458 glRotatef(30.0, 1.0, 0.0, 0.0);
459 gltrackball_rotate (qs->trackball);
460 glRotatef(qs->theta*100, 0.0, 1.0, 0.0);
461 glTranslatef(-0.5*qs->BOARDSIZE, 0.0, -0.5*qs->BOARDSIZE);
463 /* find light positions */
464 qs->position[0] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*-sin(qs->theta*100*M_PI/180.0);
465 qs->position[2] = qs->BOARDSIZE/2.0 + qs->BOARDSIZE/1.4*cos(qs->theta*100*M_PI/180.0);
466 qs->position[1] = 6.0;
469 glEnable(GL_LIGHTING);
470 glLightfv(GL_LIGHT0, GL_POSITION, qs->position);
474 /* Since the lighting attenuation trick up there doesn't seem to be working,
475 let's drop the old board down and drop the new board in. */
476 if (qs->steps < (max/8.0)) {
477 GLfloat y = qs->steps / (max/8.0);
478 y = sin (M_PI/2 * y);
479 glTranslatef (0, 10 - (y * 10), 0);
480 } else if (qs->steps > max-(max/8.0)) {
481 GLfloat y = (qs->steps - (max-(max/8.0))) / (GLfloat) (max/8.0);
482 y = 1 - sin (M_PI/2 * (1-y));
483 glTranslatef (0, -y * 15, 0);
486 /* draw reflections */
488 polys += draw_reflections(qs);
491 polys += drawBoard(qs);
495 glLightf(GL_LIGHT0, GL_LINEAR_ATTENUATION, 0.1);
497 glTranslatef(0.5, 0.0, 0.5);
498 polys += drawPieces(qs);
501 if(!qs->button_down_p)
504 /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
505 if(++qs->steps == max) {
508 qs->BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
509 qs->colorset = (qs->colorset+1)%COLORSETS;
515 static const GLfloat spidermodel[][3] =
535 #define EPSILON 0.001
538 /** draws cylindermodel */
539 static int draw_model(int chunks, const GLfloat model[][3], int r)
544 glRotatef(-90.0, 1.0, 0.0, 0.0);
546 for(i = 0; i < chunks; ++i) {
547 if(model[i][0] > EPSILON || model[i][1] > EPSILON) {
548 polys += tube (0, 0, 0,
551 r, False, False, False);
552 /* gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
555 glTranslatef(0.0, 0.0, model[i][2]);
563 ENTRYPOINT void reshape_queens(ModeInfo *mi, int width, int height)
565 GLfloat h = (GLfloat) height / (GLfloat) width;
566 glViewport(0,0, width, height);
567 glMatrixMode(GL_PROJECTION);
569 gluPerspective(45, 1/h, 2.0, 30.0);
570 glMatrixMode(GL_MODELVIEW);
573 ENTRYPOINT void init_queens(ModeInfo *mi)
575 int screen = MI_SCREEN(mi);
577 int poly_counts[PIECES];
578 wire = MI_IS_WIREFRAME(mi);
580 # ifdef HAVE_JWZGLES /* #### glPolygonMode other than GL_FILL unimplemented */
585 !(qss = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
589 qs->window = MI_WINDOW(mi);
591 if((qs->glx_context = init_GL(mi)))
592 reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
596 qs->trackball = gltrackball_init ();
598 qs->BOARDSIZE = 8; /* 8 cuz its classic */
600 chessmodels_gen_lists(-1, poly_counts);
601 qs->queen_list = QUEEN;
602 qs->queen_polys = poly_counts[QUEEN];
604 /* find a solution */
608 ENTRYPOINT void draw_queens(ModeInfo *mi)
610 Queenscreen *qs = &qss[MI_SCREEN(mi)];
611 Window w = MI_WINDOW(mi);
612 Display *disp = MI_DISPLAY(mi);
617 glXMakeCurrent(disp, w, *(qs->glx_context));
620 glShadeModel(GL_FLAT);
622 clearbits = GL_COLOR_BUFFER_BIT;
624 glColorMaterial(GL_FRONT, GL_DIFFUSE);
625 glEnable(GL_COLOR_MATERIAL);
629 glEnable(GL_DEPTH_TEST);
630 clearbits |= GL_DEPTH_BUFFER_BIT;
631 clearbits |= GL_STENCIL_BUFFER_BIT;
632 glEnable(GL_CULL_FACE);
636 glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
638 mi->polygon_count = display(qs);
639 mi->recursion_depth = qs->BOARDSIZE;
641 if(mi->fps_p) do_fps(mi);
643 glXSwapBuffers(disp, w);
646 ENTRYPOINT void release_queens(ModeInfo *mi)
655 XSCREENSAVER_MODULE ("Queens", queens)