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 (tennessb@unbc.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
20 #include <X11/Intrinsic.h>
23 # define PROGCLASS "Queens"
24 # define HACK_INIT init_queens
25 # define HACK_DRAW draw_queens
26 # define HACK_RESHAPE reshape_queens
27 # define HACK_HANDLE_EVENT queens_handle_event
28 # define EVENT_MASK PointerMotionMask
29 # define queens_opts xlockmore_opts
31 #define DEFAULTS "*delay: 20000 \n" \
32 "*showFPS: False \n" \
33 "*wireframe: False \n" \
35 # include "xlockmore.h"
44 #include "gltrackball.h"
47 #define countof(x) (sizeof((x))/sizeof((*x)))
49 static XrmOptionDescRec opts[] = {
50 {"+rotate", ".queens.rotate", XrmoptionNoArg, (caddr_t) "false" },
51 {"-rotate", ".queens.rotate", XrmoptionNoArg, (caddr_t) "true" },
52 /* {"-white", ".queens.white", XrmoptionSepArg, (cadd_t) NULL }, */
53 /* {"-black", ".queens.white", XrmoptionSepArg, (cadd_t) NULL }, */
56 int rotate, wire, clearbits;
58 static argtype vars[] = {
59 {(caddr_t *) &rotate, "rotate", "Rotate", "True", t_Bool},
62 ModeSpecOpt queens_opts = {countof(opts), opts, countof(vars), vars, NULL};
65 ModStruct queens_description =
66 {"queens", "init_queens", "draw_queens", "release_queens",
67 "draw_queens", "init_queens", NULL, &queens_opts,
68 1000, 1, 2, 1, 4, 1.0, "",
74 GLXContext *glx_context;
76 trackball_state *trackball;
80 static Queenscreen *qs = NULL;
88 #define M_PI 3.14159265
97 /* definition of white/black colors */
98 GLfloat colors[COLORSETS][2][3] =
100 {{0.5, 0.7, 0.9}, {0.2, 0.3, 0.6}},
101 {{0.53725490196, 0.360784313725, 0.521568627451}, {0.6, 0.6, 0.6}},
102 {{1.0, 0.5, 0.0}, {0.5, 0.5, 0.5}},
105 int board[MAXBOARD][MAXBOARD];
106 int steps = 0, colorset = 0, BOARDSIZE = 8; /* 8 cuz its classic */
109 queens_handle_event (ModeInfo *mi, XEvent *event)
111 Queenscreen *c = &qs[MI_SCREEN(mi)];
113 if (event->xany.type == ButtonPress &&
114 event->xbutton.button & Button1)
116 c->button_down_p = True;
117 gltrackball_start (c->trackball,
118 event->xbutton.x, event->xbutton.y,
119 MI_WIDTH (mi), MI_HEIGHT (mi));
122 else if (event->xany.type == ButtonRelease &&
123 event->xbutton.button & Button1)
125 c->button_down_p = False;
128 else if (event->xany.type == MotionNotify &&
131 gltrackball_track (c->trackball,
132 event->xmotion.x, event->xmotion.y,
133 MI_WIDTH (mi), MI_HEIGHT (mi));
142 /* returns true if placing a queen on column c causes a conflict */
143 int conflictsCols(int c) {
146 for(i = 0; i < BOARDSIZE; ++i)
153 /* returns true if placing a queen on (r,c) causes a diagonal conflict */
154 int conflictsDiag(int r, int c) {
158 int n = r < c ? r : c;
159 for(i = 0; i < BOARDSIZE-abs(r-c); ++i)
160 if(board[r-n+i][c-n+i])
164 n = r < BOARDSIZE - (c+1) ? r : BOARDSIZE - (c+1);
165 for(i = 0; i < BOARDSIZE-abs(BOARDSIZE - (1+r+c)); ++i)
166 if(board[r-n+i][c+n-i])
172 /* returns true if placing a queen at (r,c) causes a conflict */
173 int conflicts(int r, int c) {
174 return !conflictsCols(c) ? conflictsDiag(r, c) : 1;
181 for(i = 0; i < MAXBOARD; ++i)
182 for(j = 0; j < MAXBOARD; ++j)
186 /* recursively determine solution */
187 int findSolution(int row, int col) {
191 while(col < BOARDSIZE) {
192 if(!conflicts(row, col)) {
195 if(findSolution(row+1, 0))
207 /** driver for finding solution */
208 void go(void) { while(!findSolution(0, random()%BOARDSIZE)); }
210 /* configure lighting */
211 void setup_lights(void) {
212 GLfloat position[] = { 4.0, 8.0, 4.0, 1.0 };
214 glEnable(GL_LIGHTING);
215 glLightfv(GL_LIGHT0, GL_POSITION, position);
219 /* return alpha value for fading */
220 GLfloat findAlpha(void) {
221 return steps < 128 ? steps/128.0 : steps < 512-128 ? 1.0 : (512-steps)/128.0;
225 void drawPieces(void) {
228 for(i = 0; i < BOARDSIZE; ++i) {
229 for(j = 0; j < BOARDSIZE; ++j) {
231 glColor3fv(colors[colorset][i%2]);
235 glTranslatef(1.0, 0.0, 0.0);
238 glTranslatef(-1.0*BOARDSIZE, 0.0, 1.0);
243 void drawBoard(void) {
248 for(i = 0; i < BOARDSIZE; ++i)
249 for(j = 0; j < BOARDSIZE; ++j) {
250 int par = (i-j+BOARDSIZE)%2;
251 glColor3fv(colors[colorset][par]);
252 glNormal3f(0.0, 1.0, 0.0);
253 glVertex3f(i, 0.0, j + 1.0);
254 glVertex3f(i + 1.0, 0.0, j + 1.0);
255 glVertex3f(i + 1.0, 0.0, j);
256 glVertex3f(i, 0.0, j);
258 /* draw the bottom, too */
259 glNormal3f(0.0, -1.0, 0.0);
260 glVertex3f(i, 0.0, j);
261 glVertex3f(i + 1.0, 0.0, j);
262 glVertex3f(i + 1.0, 0.0, j + 1.0);
263 glVertex3f(i, 0.0, j + 1.0);
271 void display(Queenscreen *c) {
274 glMatrixMode(GL_MODELVIEW);
277 glLightf(GL_LIGHT0, GL_CONSTANT_ATTENUATION, 0.8/(0.01+findAlpha()));
279 /** setup perspectif */
280 glTranslatef(0.0, 0.0, -1.5*BOARDSIZE);
281 glRotatef(30.0, 1.0, 0.0, 0.0);
282 gltrackball_rotate (c->trackball);
283 glRotatef(theta*100, 0.0, 1.0, 0.0);
284 glTranslatef(-0.5*BOARDSIZE, 0.0, -0.5*BOARDSIZE);
287 glTranslatef(0.5, 0.01, 0.5);
290 if (!c->button_down_p)
293 /* zero out board, find new solution of size MINBOARD <= i <= MAXBOARD */
297 BOARDSIZE = MINBOARD + (random() % (MAXBOARD - MINBOARD + 1));
298 colorset = (colorset+1)%COLORSETS;
304 GLfloat spidermodel[][3] =
323 #define EPSILON 0.001
325 /** draws cylindermodel */
326 void draw_model(int chunks, GLfloat model[][3], int r) {
328 GLUquadricObj *quadric = gluNewQuadric();
330 glRotatef(-90.0, 1.0, 0.0, 0.0);
332 for(i = 0; i < chunks; ++i) {
333 if(model[i][0] > EPSILON || model[i][1] > EPSILON)
334 gluCylinder(quadric, model[i][0], model[i][1], model[i][2], r, 1);
335 glTranslatef(0.0, 0.0, model[i][2]);
341 void reshape_queens(ModeInfo *mi, int width, int height) {
342 GLfloat h = (GLfloat) height / (GLfloat) width;
343 glViewport(0,0, width, height);
344 glMatrixMode(GL_PROJECTION);
346 gluPerspective(45, 1/h, 2.0, 30.0);
347 glMatrixMode(GL_MODELVIEW);
350 void init_queens(ModeInfo *mi) {
351 int screen = MI_SCREEN(mi);
353 wire = MI_IS_WIREFRAME(mi);
356 !(qs = (Queenscreen *) calloc(MI_NUM_SCREENS(mi), sizeof(Queenscreen))))
360 c->window = MI_WINDOW(mi);
361 c->trackball = gltrackball_init ();
363 if((c->glx_context = init_GL(mi)))
364 reshape_queens(mi, MI_WIDTH(mi), MI_HEIGHT(mi));
368 glClearColor(0.0, 0.0, 0.0, 0.0);
369 glNewList(1, GL_COMPILE);
370 draw_model(schunks, spidermodel, 24);
373 clearbits = GL_COLOR_BUFFER_BIT;
375 glColorMaterial(GL_FRONT, GL_DIFFUSE);
376 glEnable(GL_COLOR_MATERIAL);
380 glEnable(GL_DEPTH_TEST);
381 clearbits |= GL_DEPTH_BUFFER_BIT;
382 glEnable(GL_CULL_FACE);
386 glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
388 /* find a solution */
392 void draw_queens(ModeInfo *mi) {
393 Queenscreen *c = &qs[MI_SCREEN(mi)];
394 Window w = MI_WINDOW(mi);
395 Display *disp = MI_DISPLAY(mi);
400 glXMakeCurrent(disp, w, *(c->glx_context));
404 if(mi->fps_p) do_fps(mi);
406 glXSwapBuffers(disp, w);
409 void release_queens(ModeInfo *mi) {