]> ncurses.scripts.mit.edu Git - ncurses.git/blob - test/knight.c
ncurses 5.7 - patch 20100417
[ncurses.git] / test / knight.c
1 /****************************************************************************
2  * Copyright (c) 1998-2006,2008 Free Software Foundation, Inc.              *
3  *                                                                          *
4  * Permission is hereby granted, free of charge, to any person obtaining a  *
5  * copy of this software and associated documentation files (the            *
6  * "Software"), to deal in the Software without restriction, including      *
7  * without limitation the rights to use, copy, modify, merge, publish,      *
8  * distribute, distribute with modifications, sublicense, and/or sell       *
9  * copies of the Software, and to permit persons to whom the Software is    *
10  * furnished to do so, subject to the following conditions:                 *
11  *                                                                          *
12  * The above copyright notice and this permission notice shall be included  *
13  * in all copies or substantial portions of the Software.                   *
14  *                                                                          *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
16  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
18  * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
19  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
20  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
21  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
22  *                                                                          *
23  * Except as contained in this notice, the name(s) of the above copyright   *
24  * holders shall not be used in advertising or otherwise to promote the     *
25  * sale, use or other dealings in this Software without prior written       *
26  * authorization.                                                           *
27  ****************************************************************************/
28 /*
29  * Knight's Tour - a brain game
30  *
31  * The original of this game was anonymous.  It had an unbelievably bogus
32  * interface, you actually had to enter square coordinates!  Redesign by
33  * Eric S. Raymond <esr@snark.thyrsus.com> July 22 1995.  Mouse support
34  * added September 20th 1995.
35  *
36  * $Id: knight.c,v 1.28 2008/08/03 23:04:26 tom Exp $
37  */
38
39 #include <test.priv.h>
40
41 /* board size */
42 #define BDEPTH  8
43 #define BWIDTH  8
44
45 /* where to start the instructions */
46 #define INSTRY  2
47 #define INSTRX  35
48
49 /* corner of board */
50 #define BOARDY  2
51 #define BOARDX  0
52
53 /* notification line */
54 #define NOTIFYY 21
55
56 /* virtual color values */
57 #define TRAIL_COLOR     1
58 #define PLUS_COLOR      2
59 #define MINUS_COLOR     3
60
61 #define CX(x)           (2 + 4 * (x))
62 #define CY(y)           (1 + 2 * (y))
63 #define cellmove(y, x)  wmove(boardwin, CY(y), CX(x))
64 #define CXINV(x)        (((x) - 1) / 4)
65 #define CYINV(y)        (((y) - 2) / 2)
66
67 typedef struct {
68     short x, y;
69 } cell;
70
71 static WINDOW *boardwin;        /* the board window */
72 static WINDOW *helpwin;         /* the help window */
73 static WINDOW *msgwin;          /* the message window */
74 static cell history[BDEPTH * BWIDTH + 1];       /* choice history */
75 static chtype minus = '-';      /* possible-move character */
76 static chtype oldch;
77 static chtype plus = '+';       /* cursor hot-spot character */
78 static chtype trail = '#';      /* trail character */
79 static int movecount;           /* count of moves so far */
80 static int trialcount;          /* count of trials so far */
81 static short board[BDEPTH][BWIDTH];     /* the squares */
82 /* *INDENT-OFF* */
83 static const struct {
84     int y;
85     int x;
86 } offsets[] = {
87     {  2,  1 },
88     {  1,  2 },
89     { -1,  2 },
90     { -2,  1 },
91     { -2, -1 },
92     { -1, -2 },
93     {  1, -2 },
94     {  2, -1 },
95 };
96 /* *INDENT-ON* */
97
98 static void
99 init_program(void)
100 {
101     setlocale(LC_ALL, "");
102
103     srand((unsigned) getpid());
104     initscr();
105     cbreak();                   /* immediate char return */
106     noecho();                   /* no immediate echo */
107     boardwin = newwin(BDEPTH * 2 + 1, BWIDTH * 4 + 1, BOARDY, BOARDX);
108     helpwin = newwin(0, 0, INSTRY, INSTRX);
109     msgwin = newwin(1, INSTRX - 1, NOTIFYY, 0);
110     scrollok(msgwin, TRUE);
111     keypad(boardwin, TRUE);
112
113     if (has_colors()) {
114         int bg = COLOR_BLACK;
115
116         start_color();
117 #if HAVE_USE_DEFAULT_COLORS
118         if (use_default_colors() == OK)
119             bg = -1;
120 #endif
121
122         (void) init_pair(TRAIL_COLOR, COLOR_CYAN, bg);
123         (void) init_pair(PLUS_COLOR, COLOR_RED, bg);
124         (void) init_pair(MINUS_COLOR, COLOR_GREEN, bg);
125
126         trail |= COLOR_PAIR(TRAIL_COLOR);
127         plus |= COLOR_PAIR(PLUS_COLOR);
128         minus |= COLOR_PAIR(MINUS_COLOR);
129     }
130 #ifdef NCURSES_MOUSE_VERSION
131     (void) mousemask(BUTTON1_CLICKED, (mmask_t *) NULL);
132 #endif /* NCURSES_MOUSE_VERSION */
133
134     oldch = minus;
135 }
136
137 static void
138 help1(void)
139 /* game explanation -- initial help screen */
140 {
141     (void) waddstr(helpwin, "Knight's move is a solitaire puzzle.  Your\n");
142     (void) waddstr(helpwin, "objective is to visit each square of the  \n");
143     (void) waddstr(helpwin, "chessboard exactly once by making knight's\n");
144     (void) waddstr(helpwin, "moves (one square right or left followed  \n");
145     (void) waddstr(helpwin, "by two squares up or down, or two squares \n");
146     (void) waddstr(helpwin, "right or left followed by one square up or\n");
147     (void) waddstr(helpwin, "down).  You may start anywhere.\n\n");
148
149     (void) waddstr(helpwin, "Use arrow keys to move the cursor around.\n");
150     (void) waddstr(helpwin, "When you want to move your knight to the \n");
151     (void) waddstr(helpwin, "cursor location, press <space> or Enter.\n");
152     (void) waddstr(helpwin, "Illegal moves will be rejected with an  \n");
153     (void) waddstr(helpwin, "audible beep.\n\n");
154     (void) waddstr(helpwin, "The program will detect if you solve the\n");
155     (void) waddstr(helpwin, "puzzle; also inform you when you run out\n");
156     (void) waddstr(helpwin, "of legal moves.\n\n");
157
158     (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0,
159                      "Press `?' to go to keystroke help.");
160 }
161
162 static void
163 help2(void)
164 /* keystroke help screen */
165 {
166     (void) waddstr(helpwin, "Possible moves are shown with `-'.\n\n");
167
168     (void) waddstr(helpwin, "You can move around with the arrow keys or\n");
169     (void) waddstr(helpwin, "with the rogue/hack movement keys.  Other\n");
170     (void) waddstr(helpwin, "commands allow you to undo moves or redraw.\n");
171     (void) waddstr(helpwin, "Your mouse may work; try left-button to\n");
172     (void) waddstr(helpwin, "move to the square under the pointer.\n\n");
173
174     (void) waddstr(helpwin, "x,q -- exit             y k u    7 8 9\n");
175     (void) waddstr(helpwin, "r -- redraw screen       \\|/      \\|/ \n");
176     (void) waddstr(helpwin, "bksp -- undo move       h-+-l    4-+-6\n");
177     (void) waddstr(helpwin, "a -- autojump            /|\\      /|\\ \n");
178     (void) waddstr(helpwin, "                        b j n    1 2 3\n");
179
180     (void) waddstr(helpwin, "\nYou can place your knight on the selected\n");
181     (void) waddstr(helpwin, "square with spacebar, Enter, or the keypad\n");
182     (void) waddstr(helpwin, "center key.  Use F/B to review the path.\n");
183
184     (void) mvwaddstr(helpwin, NOTIFYY - INSTRY, 0,
185                      "Press `?' to go to game explanation");
186 }
187
188 static void
189 show_help(bool * keyhelp)
190 {
191     werase(helpwin);
192     if (*keyhelp) {
193         help1();
194         *keyhelp = FALSE;
195     } else {
196         help2();
197         *keyhelp = TRUE;
198     }
199     wrefresh(helpwin);
200 }
201
202 static bool
203 chksqr(int r1, int c1)
204 {
205     if ((r1 < 0) || (r1 > BDEPTH - 1))
206         return (FALSE);
207     if ((c1 < 0) || (c1 > BWIDTH - 1))
208         return (FALSE);
209     return ((!board[r1][c1]) ? TRUE : FALSE);
210 }
211
212 static bool
213 chkmoves(int rw, int col)
214 /* check to see if valid moves are available */
215 {
216     unsigned n;
217
218     for (n = 0; n < SIZEOF(offsets); n++)
219         if (chksqr(rw + offsets[n].y, col + offsets[n].x))
220             return (TRUE);
221     return (FALSE);
222 }
223
224 static void
225 dosquares(void)
226 {
227     int i, j;
228
229     mvaddstr(0, 20, "KNIGHT'S MOVE -- a logical solitaire");
230
231     move(BOARDY, BOARDX);
232     waddch(boardwin, ACS_ULCORNER);
233     for (j = 0; j < 7; j++) {
234         waddch(boardwin, ACS_HLINE);
235         waddch(boardwin, ACS_HLINE);
236         waddch(boardwin, ACS_HLINE);
237         waddch(boardwin, ACS_TTEE);
238     }
239     waddch(boardwin, ACS_HLINE);
240     waddch(boardwin, ACS_HLINE);
241     waddch(boardwin, ACS_HLINE);
242     waddch(boardwin, ACS_URCORNER);
243
244     for (i = 1; i < BDEPTH; i++) {
245         move(BOARDY + i * 2 - 1, BOARDX);
246         waddch(boardwin, ACS_VLINE);
247         for (j = 0; j < BWIDTH; j++) {
248             waddch(boardwin, ' ');
249             waddch(boardwin, ' ');
250             waddch(boardwin, ' ');
251             waddch(boardwin, ACS_VLINE);
252         }
253         move(BOARDY + i * 2, BOARDX);
254         waddch(boardwin, ACS_LTEE);
255         for (j = 0; j < BWIDTH - 1; j++) {
256             waddch(boardwin, ACS_HLINE);
257             waddch(boardwin, ACS_HLINE);
258             waddch(boardwin, ACS_HLINE);
259             waddch(boardwin, ACS_PLUS);
260         }
261         waddch(boardwin, ACS_HLINE);
262         waddch(boardwin, ACS_HLINE);
263         waddch(boardwin, ACS_HLINE);
264         waddch(boardwin, ACS_RTEE);
265     }
266
267     move(BOARDY + i * 2 - 1, BOARDX);
268     waddch(boardwin, ACS_VLINE);
269     for (j = 0; j < BWIDTH; j++) {
270         waddch(boardwin, ' ');
271         waddch(boardwin, ' ');
272         waddch(boardwin, ' ');
273         waddch(boardwin, ACS_VLINE);
274     }
275
276     move(BOARDY + i * 2, BOARDX);
277     waddch(boardwin, ACS_LLCORNER);
278     for (j = 0; j < BWIDTH - 1; j++) {
279         waddch(boardwin, ACS_HLINE);
280         waddch(boardwin, ACS_HLINE);
281         waddch(boardwin, ACS_HLINE);
282         waddch(boardwin, ACS_BTEE);
283     }
284     waddch(boardwin, ACS_HLINE);
285     waddch(boardwin, ACS_HLINE);
286     waddch(boardwin, ACS_HLINE);
287     waddch(boardwin, ACS_LRCORNER);
288 }
289
290 static void
291 mark_possibles(int prow, int pcol, chtype mark)
292 {
293     unsigned n;
294
295     for (n = 0; n < SIZEOF(offsets); n++) {
296         if (chksqr(prow + offsets[n].y, pcol + offsets[n].x)) {
297             cellmove(prow + offsets[n].y, pcol + offsets[n].x);
298             waddch(boardwin, mark);
299         }
300     }
301 }
302
303 static void
304 find_next_move(int *y, int *x)
305 {
306     unsigned j, k;
307     int found = -1;
308     int first = -1;
309     int next = 0;
310     int oldy, oldx;
311     int newy, newx;
312
313     if (movecount > 1) {
314         oldy = history[movecount - 1].y;
315         oldx = history[movecount - 1].x;
316         for (j = 0; j < SIZEOF(offsets) * 2; j++) {
317             k = j % SIZEOF(offsets);
318             newy = oldy + offsets[k].y;
319             newx = oldx + offsets[k].x;
320             if (chksqr(newy, newx)) {
321                 if (first < 0)
322                     first = k;
323                 if (newy == *y
324                     && newx == *x) {
325                     found = k;
326                 } else if (found >= 0) {
327                     next = k;
328                     break;
329                 }
330             }
331         }
332         if (found < 0)
333             next = first;
334         if (next >= 0) {
335             *y = oldy + offsets[next].y;
336             *x = oldx + offsets[next].x;
337         }
338     } else {
339         beep();
340     }
341 }
342
343 static void
344 unmarkcell(int row, int column)
345 {
346     cellmove(row, column);
347     waddch(boardwin, '\b');
348     waddch(boardwin, ' ');
349     waddch(boardwin, minus);
350     waddch(boardwin, ' ');
351 }
352
353 static void
354 markcell(chtype tchar, int row, int column)
355 {
356     cellmove(row, column);
357     waddch(boardwin, '\b');
358     waddch(boardwin, tchar);
359     waddch(boardwin, tchar);
360     waddch(boardwin, tchar);
361 }
362
363 static void
364 drawmove(chtype tchar, int oldy, int oldx, int row, int column)
365 /* place the stars, update board & currents */
366 {
367     if (movecount <= 1) {
368         int i, j;
369
370         for (i = 0; i < BDEPTH; i++) {
371             for (j = 0; j < BWIDTH; j++) {
372                 if (movecount == 0) {
373                     unmarkcell(i, j);
374                 } else {
375                     cellmove(i, j);
376                     if (winch(boardwin) == minus)
377                         waddch(boardwin, movecount ? ' ' : minus);
378                 }
379             }
380         }
381     } else {
382         markcell(tchar, oldy, oldx);
383         mark_possibles(oldy, oldx, ' ');
384     }
385
386     if (row >= 0 && column >= 0) {
387         markcell(trail, row, column);
388         mark_possibles(row, column, minus);
389         board[row][column] = TRUE;
390     }
391
392     wprintw(msgwin, "\nMove %d", movecount);
393     if (trialcount != movecount)
394         wprintw(msgwin, " (%d tries)", trialcount);
395     wclrtoeol(msgwin);
396 }
397
398 static int
399 iabs(int num)
400 {
401     if (num < 0)
402         return (-num);
403     else
404         return (num);
405 }
406
407 static bool
408 evalmove(int row, int column)
409 /* evaluate move */
410 {
411     if (movecount == 1)
412         return (TRUE);
413     else if (board[row][column] == TRUE) {
414         waddstr(msgwin, "\nYou've already been there.");
415         return (FALSE);
416     } else {
417         int rdif = iabs(row - history[movecount - 1].y);
418         int cdif = iabs(column - history[movecount - 1].x);
419
420         if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) {
421             waddstr(msgwin, "\nThat's not a legal knight's move.");
422             return (FALSE);
423         }
424     }
425
426     return (TRUE);
427 }
428
429 static int
430 completed(void)
431 {
432     int i, j, count = 0;
433
434     for (i = 0; i < BDEPTH; i++)
435         for (j = 0; j < BWIDTH; j++)
436             if (board[i][j] != 0)
437                 count += 1;
438     return (count == (BWIDTH * BDEPTH) ? -1 : count);
439 }
440
441 static void
442 no_previous_move(void)
443 {
444     waddstr(msgwin, "\nNo previous move.");
445     beep();
446 }
447
448 static void
449 play(void)
450 /* play the game */
451 {
452     bool keyhelp;               /* TRUE if keystroke help is up */
453     int i, j, count;
454     int lastcol = 0;            /* last location visited */
455     int lastrow = 0;
456     int ny = 0, nx = 0;
457     int review = 0;             /* review history */
458     int rw = 0, col = 0;        /* current row and column */
459
460     do {
461         /* clear screen and draw board */
462         werase(boardwin);
463         werase(helpwin);
464         werase(msgwin);
465         dosquares();
466         help1();
467         wnoutrefresh(stdscr);
468         wnoutrefresh(helpwin);
469         wnoutrefresh(msgwin);
470         wnoutrefresh(boardwin);
471         doupdate();
472
473         movecount = 0;
474         for (i = 0; i < BDEPTH; i++) {
475             for (j = 0; j < BWIDTH; j++) {
476                 board[i][j] = FALSE;
477                 unmarkcell(i, j);
478             }
479         }
480         memset(history, 0, sizeof(history));
481         history[0].y = history[0].x = -1;
482         history[1].y = history[1].x = -1;
483         lastrow = lastcol = -2;
484         movecount = 1;
485         trialcount = 1;
486         keyhelp = FALSE;
487         show_help(&keyhelp);
488
489         for (;;) {
490             if (rw != lastrow || col != lastcol) {
491                 if (lastrow >= 0 && lastcol >= 0) {
492                     cellmove(lastrow, lastcol);
493                     if (board[lastrow][lastcol])
494                         waddch(boardwin, trail);
495                     else
496                         waddch(boardwin, oldch);
497                 }
498
499                 cellmove(rw, col);
500                 oldch = winch(boardwin);
501
502                 lastrow = rw;
503                 lastcol = col;
504             }
505             cellmove(rw, col);
506             waddch(boardwin, plus);
507             cellmove(rw, col);
508
509             wrefresh(msgwin);
510
511             switch (wgetch(boardwin)) {
512             case 'k':
513             case '8':
514             case KEY_UP:
515                 ny = rw + BDEPTH - 1;
516                 nx = col;
517                 break;
518             case 'j':
519             case '2':
520             case KEY_DOWN:
521                 ny = rw + 1;
522                 nx = col;
523                 break;
524             case 'h':
525             case '4':
526             case KEY_LEFT:
527                 ny = rw;
528                 nx = col + BWIDTH - 1;
529                 break;
530             case 'l':
531             case '6':
532             case KEY_RIGHT:
533                 ny = rw;
534                 nx = col + 1;
535                 break;
536             case 'y':
537             case '7':
538             case KEY_A1:
539                 ny = rw + BDEPTH - 1;
540                 nx = col + BWIDTH - 1;
541                 break;
542             case 'b':
543             case '1':
544             case KEY_C1:
545                 ny = rw + 1;
546                 nx = col + BWIDTH - 1;
547                 break;
548             case 'u':
549             case '9':
550             case KEY_A3:
551                 ny = rw + BDEPTH - 1;
552                 nx = col + 1;
553                 break;
554             case 'n':
555             case '3':
556             case KEY_C3:
557                 ny = rw + 1;
558                 nx = col + 1;
559                 break;
560
561 #ifdef NCURSES_MOUSE_VERSION
562             case KEY_MOUSE:
563                 {
564                     MEVENT myevent;
565
566                     getmouse(&myevent);
567                     if (myevent.y >= CY(0) && myevent.y <= CY(BDEPTH)
568                         && myevent.x >= CX(0) && myevent.x <= CX(BWIDTH)) {
569                         nx = CXINV(myevent.x);
570                         ny = CYINV(myevent.y);
571                         ungetch('\n');
572                         break;
573                     } else {
574                         beep();
575                         continue;
576                     }
577                 }
578 #endif /* NCURSES_MOUSE_VERSION */
579
580             case KEY_B2:
581             case '\n':
582             case ' ':
583                 review = 0;
584                 if (evalmove(rw, col)) {
585                     drawmove(trail,
586                              history[movecount - 1].y,
587                              history[movecount - 1].x,
588                              rw, col);
589                     history[movecount].y = rw;
590                     history[movecount].x = col;
591                     movecount++;
592                     trialcount++;
593
594                     if (!chkmoves(rw, col)) {
595                         if (completed() < 0) {
596                             waddstr(msgwin, "\nYou won.");
597                         } else {
598                             waddstr(msgwin,
599                                     "\nNo further moves are possible.");
600                         }
601                     }
602                 } else {
603                     beep();
604                 }
605                 break;
606
607             case KEY_UNDO:
608             case KEY_BACKSPACE:
609             case '\b':
610                 review = 0;
611                 if (movecount <= 0) {
612                     no_previous_move();
613                 } else if (movecount <= 1) {
614                     ny = history[movecount].y;
615                     nx = history[movecount].x;
616                     if (nx < 0 || ny < 0) {
617                         ny = lastrow;
618                         nx = lastcol;
619                     }
620                     movecount = 0;
621                     board[ny][nx] = FALSE;
622                     oldch = minus;
623                     drawmove(' ', ny, nx, -1, -1);
624                     movecount = 1;
625                     trialcount = 1;
626                     no_previous_move();
627                 } else {
628                     int oldy = history[movecount - 1].y;
629                     int oldx = history[movecount - 1].x;
630
631                     if (!board[rw][col]) {
632                         cellmove(rw, col);
633                         waddch(boardwin, ' ');
634                     }
635
636                     board[oldy][oldx] = FALSE;
637                     --movecount;
638                     ny = history[movecount - 1].y;
639                     nx = history[movecount - 1].x;
640                     if (nx < 0 || ny < 0) {
641                         ny = oldy;
642                         nx = oldx;
643                     }
644                     drawmove(' ', oldy, oldx, ny, nx);
645
646                     /* avoid problems if we just changed the current cell */
647                     cellmove(lastrow, lastcol);
648                     oldch = winch(boardwin);
649                 }
650                 break;
651
652             case 'a':
653                 nx = col;
654                 ny = rw;
655                 find_next_move(&ny, &nx);
656                 break;
657
658             case 'F':
659                 if (review > 0) {
660                     review--;
661                     ny = history[movecount - review - 1].y;
662                     nx = history[movecount - review - 1].x;
663                 } else {
664                     beep();
665                 }
666                 break;
667
668             case 'B':
669                 if (review < movecount - 2) {
670                     review++;
671                     ny = history[movecount - review - 1].y;
672                     nx = history[movecount - review - 1].x;
673                 } else {
674                     beep();
675                 }
676                 break;
677
678             case KEY_REDO:
679             case '\f':
680             case 'r':
681                 clearok(curscr, TRUE);
682                 wnoutrefresh(stdscr);
683                 wnoutrefresh(boardwin);
684                 wnoutrefresh(msgwin);
685                 wnoutrefresh(helpwin);
686                 doupdate();
687                 break;
688
689             case 'q':
690             case 'x':
691                 goto dropout;
692
693             case '?':
694                 show_help(&keyhelp);
695                 break;
696
697             default:
698                 beep();
699                 break;
700             }
701
702             col = nx % BWIDTH;
703             rw = ny % BDEPTH;
704         }
705
706       dropout:
707         if ((count = completed()) < 0)
708             wprintw(msgwin, "\nYou won.  Care to try again? ");
709         else
710             wprintw(msgwin, "\n%d squares filled.  Try again? ", count);
711         wclrtoeol(msgwin);
712     } while
713         (tolower(wgetch(msgwin)) == 'y');
714 }
715
716 int
717 main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
718 {
719     init_program();
720
721     play();
722
723     endwin();
724     ExitProgram(EXIT_SUCCESS);
725 }
726
727 /* knight.c ends here */