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
67typedef struct {
68    short x, y;
69} cell;
70
71static WINDOW *boardwin;	/* the board window */
72static WINDOW *helpwin;		/* the help window */
73static WINDOW *msgwin;		/* the message window */
74static cell history[BDEPTH * BWIDTH + 1];	/* choice history */
75static chtype minus = '-';	/* possible-move character */
76static chtype oldch;
77static chtype plus = '+';	/* cursor hot-spot character */
78static chtype trail = '#';	/* trail character */
79static int movecount;		/* count of moves so far */
80static int trialcount;		/* count of trials so far */
81static short board[BDEPTH][BWIDTH];	/* the squares */
82/* *INDENT-OFF* */
83static 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
98static void
99init_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
137static void
138help1(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
162static void
163help2(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
188static void
189show_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
202static bool
203chksqr(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
212static bool
213chkmoves(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
224static void
225dosquares(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
290static void
291mark_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
303static void
304find_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
343static void
344unmarkcell(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
353static void
354markcell(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
363static void
364drawmove(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
398static int
399iabs(int num)
400{
401    if (num < 0)
402	return (-num);
403    else
404	return (num);
405}
406
407static bool
408evalmove(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
429static int
430completed(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
441static void
442no_previous_move(void)
443{
444    waddstr(msgwin, "\nNo previous move.");
445    beep();
446}
447
448static void
449play(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
716int
717main(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 */
728