test/knight.c

/****************************************************************************
 * Copyright (c) 1998-2012,2013 Free Software Foundation, Inc.              *
 *                                                                          *
 * Permission is hereby granted, free of charge, to any person obtaining a  *
 * copy of this software and associated documentation files (the            *
 * "Software"), to deal in the Software without restriction, including      *
 * without limitation the rights to use, copy, modify, merge, publish,      *
 * distribute, distribute with modifications, sublicense, and/or sell       *
 * copies of the Software, and to permit persons to whom the Software is    *
 * furnished to do so, subject to the following conditions:                 *
 *                                                                          *
 * The above copyright notice and this permission notice shall be included  *
 * in all copies or substantial portions of the Software.                   *
 *                                                                          *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
 * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
 *                                                                          *
 * Except as contained in this notice, the name(s) of the above copyright   *
 * holders shall not be used in advertising or otherwise to promote the     *
 * sale, use or other dealings in this Software without prior written       *
 * authorization.                                                           *
 ****************************************************************************/
/*
 * Knight's Tour - a brain game
 *
 * The original of this game was anonymous.  It had an unbelievably bogus
 * interface, you actually had to enter square coordinates!  Redesign by
 * Eric S. Raymond <esr@snark.thyrsus.com> July 22 1995.  Mouse support
 * added September 20th 1995.
 *
 * $Id: knight.c,v 1.36 2013/02/16 19:53:08 tom Exp $
 */

#include <test.priv.h>

/* board size */
#define BDEPTH	8
#define BWIDTH	8

/* where to start the instructions */
#define INSTRY	2
#define INSTRX	35

/* corner of board */
#define BOARDY	2
#define BOARDX	0

/* notification line */
#define NOTIFYY	21

/* virtual color values */
#define TRAIL_COLOR	1
#define PLUS_COLOR	2
#define MINUS_COLOR	3

#define CX(x)		(2 + 4 * (x))
#define CY(y)		(1 + 2 * (y))
#define cellmove(y, x)	wmove(boardwin, CY(y), CX(x))
#define CXINV(x)	(((x) - 1) / 4)
#define CYINV(y)	(((y) - 2) / 2)

typedef struct {
    short x, y;
} cell;

static WINDOW *boardwin;	/* the board window */
static WINDOW *helpwin;		/* the help window */
static WINDOW *msgwin;		/* the message window */
static cell history[BDEPTH * BWIDTH + 1];	/* choice history */
static chtype minus = '-';	/* possible-move character */
static chtype oldch;
static chtype plus = '+';	/* cursor hot-spot character */
static chtype trail = '#';	/* trail character */
static int movecount;		/* count of moves so far */
static int trialcount;		/* count of trials so far */
static short board[BDEPTH][BWIDTH];	/* the squares */
/* *INDENT-OFF* */
static const struct {
    int y;
    int x;
} offsets[] = {
    {  2,  1 },
    {  1,  2 },
    { -1,  2 },
    { -2,  1 },
    { -2, -1 },
    { -1, -2 },
    {  1, -2 },
    {  2, -1 },
};
/* *INDENT-ON* */

static void
init_program(void)
{
    setlocale(LC_ALL, "");

    srand((unsigned) getpid());
    initscr();
    cbreak();			/* immediate char return */
    noecho();			/* no immediate echo */
    boardwin = newwin(BDEPTH * 2 + 1, BWIDTH * 4 + 1, BOARDY, BOARDX);
    helpwin = newwin(0, 0, INSTRY, INSTRX);
    msgwin = newwin(1, INSTRX - 1, NOTIFYY, 0);
    scrollok(msgwin, TRUE);
    keypad(boardwin, TRUE);

    if (has_colors()) {
	int bg = COLOR_BLACK;

	start_color();
#if HAVE_USE_DEFAULT_COLORS
	if (use_default_colors() == OK)
	    bg = -1;
#endif

	(void) init_pair(TRAIL_COLOR, (short) COLOR_CYAN, (short) bg);
	(void) init_pair(PLUS_COLOR, (short) COLOR_RED, (short) bg);
	(void) init_pair(MINUS_COLOR, (short) COLOR_GREEN, (short) bg);

	trail |= (chtype) COLOR_PAIR(TRAIL_COLOR);
	plus |= (chtype) COLOR_PAIR(PLUS_COLOR);
	minus |= (chtype) COLOR_PAIR(MINUS_COLOR);
    }
#ifdef NCURSES_MOUSE_VERSION
    (void) mousemask(BUTTON1_CLICKED, (mmask_t *) NULL);
#endif /* NCURSES_MOUSE_VERSION */
#if defined(PDCURSES)
    mouse_set(BUTTON1_RELEASED);
#endif

    oldch = minus;
}

static void
help1(void)
/* game explanation -- initial help screen */
{
    (void) waddstr(helpwin, "Knight's move is a solitaire puzzle.  Your\n");
    (void) waddstr(helpwin, "objective is to visit each square of the  \n");
    (void) waddstr(helpwin, "chessboard exactly once by making knight's\n");
    (void) waddstr(helpwin, "moves (one square right or left followed  \n");
    (void) waddstr(helpwin, "by two squares up or down, or two squares \n");
    (void) waddstr(helpwin, "right or left followed by one square up or\n");
    (void) waddstr(helpwin, "down).  You may start anywhere.\n\n");

    (void) waddstr(helpwin, "Use arrow keys to move the cursor around.\n");
    (void) waddstr(helpwin, "When you want to move your knight to the \n");
    (void) waddstr(helpwin, "cursor location, press <space> or Enter.\n");
    (void) waddstr(helpwin, "Illegal moves will be rejected with an  \n");
    (void) waddstr(helpwin, "audible beep.\n\n");
    (void) waddstr(helpwin, "The program will detect if you solve the\n");
    (void) waddstr(helpwin, "puzzle; also inform you when you run out\n");
    (void) waddstr(helpwin, "of legal moves.\n\n");

    MvWAddStr(helpwin, NOTIFYY - INSTRY, 0,
	      "Press `?' to go to keystroke help.");
}

static void
help2(void)
/* keystroke help screen */
{
    (void) waddstr(helpwin, "Possible moves are shown with `-'.\n\n");

    (void) waddstr(helpwin, "You can move around with the arrow keys or\n");
    (void) waddstr(helpwin, "with the rogue/hack movement keys.  Other\n");
    (void) waddstr(helpwin, "commands allow you to undo moves or redraw.\n");
    (void) waddstr(helpwin, "Your mouse may work; try left-button to\n");
    (void) waddstr(helpwin, "move to the square under the pointer.\n\n");

    (void) waddstr(helpwin, "x,q -- exit             y k u    7 8 9\n");
    (void) waddstr(helpwin, "r -- redraw screen       \\|/      \\|/ \n");
    (void) waddstr(helpwin, "bksp -- undo move       h-+-l    4-+-6\n");
    (void) waddstr(helpwin, "a -- autojump            /|\\      /|\\ \n");
    (void) waddstr(helpwin, "                        b j n    1 2 3\n");

    (void) waddstr(helpwin, "\nYou can place your knight on the selected\n");
    (void) waddstr(helpwin, "square with spacebar, Enter, or the keypad\n");
    (void) waddstr(helpwin, "center key.  Use F/B to review the path.\n");

    MvWAddStr(helpwin, NOTIFYY - INSTRY, 0,
	      "Press `?' to go to game explanation");
}

static void
show_help(bool * keyhelp)
{
    werase(helpwin);
    if (*keyhelp) {
	help1();
	*keyhelp = FALSE;
    } else {
	help2();
	*keyhelp = TRUE;
    }
    wrefresh(helpwin);
}

static bool
chksqr(int r1, int c1)
{
    if ((r1 < 0) || (r1 > BDEPTH - 1))
	return (FALSE);
    if ((c1 < 0) || (c1 > BWIDTH - 1))
	return (FALSE);
    return ((!board[r1][c1]) ? TRUE : FALSE);
}

static bool
chkmoves(int rw, int col)
/* check to see if valid moves are available */
{
    unsigned n;

    for (n = 0; n < SIZEOF(offsets); n++)
	if (chksqr(rw + offsets[n].y, col + offsets[n].x))
	    return (TRUE);
    return (FALSE);
}

static void
dosquares(void)
{
    int i, j;

    MvAddStr(0, 20, "KNIGHT'S MOVE -- a logical solitaire");

    move(BOARDY, BOARDX);
    waddch(boardwin, ACS_ULCORNER);
    for (j = 0; j < 7; j++) {
	waddch(boardwin, ACS_HLINE);
	waddch(boardwin, ACS_HLINE);
	waddch(boardwin, ACS_HLINE);
	waddch(boardwin, ACS_TTEE);
    }
    waddch(boardwin, ACS_HLINE);
    waddch(boardwin, ACS_HLINE);
    waddch(boardwin, ACS_HLINE);
    waddch(boardwin, ACS_URCORNER);

    for (i = 1; i < BDEPTH; i++) {
	move(BOARDY + i * 2 - 1, BOARDX);
	waddch(boardwin, ACS_VLINE);
	for (j = 0; j < BWIDTH; j++) {
	    waddch(boardwin, ' ');
	    waddch(boardwin, ' ');
	    waddch(boardwin, ' ');
	    waddch(boardwin, ACS_VLINE);
	}
	move(BOARDY + i * 2, BOARDX);
	waddch(boardwin, ACS_LTEE);
	for (j = 0; j < BWIDTH - 1; j++) {
	    waddch(boardwin, ACS_HLINE);
	    waddch(boardwin, ACS_HLINE);
	    waddch(boardwin, ACS_HLINE);
	    waddch(boardwin, ACS_PLUS);
	}
	waddch(boardwin, ACS_HLINE);
	waddch(boardwin, ACS_HLINE);
	waddch(boardwin, ACS_HLINE);
	waddch(boardwin, ACS_RTEE);
    }

    move(BOARDY + i * 2 - 1, BOARDX);
    waddch(boardwin, ACS_VLINE);
    for (j = 0; j < BWIDTH; j++) {
	waddch(boardwin, ' ');
	waddch(boardwin, ' ');
	waddch(boardwin, ' ');
	waddch(boardwin, ACS_VLINE);
    }

    move(BOARDY + i * 2, BOARDX);
    waddch(boardwin, ACS_LLCORNER);
    for (j = 0; j < BWIDTH - 1; j++) {
	waddch(boardwin, ACS_HLINE);
	waddch(boardwin, ACS_HLINE);
	waddch(boardwin, ACS_HLINE);
	waddch(boardwin, ACS_BTEE);
    }
    waddch(boardwin, ACS_HLINE);
    waddch(boardwin, ACS_HLINE);
    waddch(boardwin, ACS_HLINE);
    waddch(boardwin, ACS_LRCORNER);
}

static void
mark_possibles(int prow, int pcol, chtype mark)
{
    unsigned n;

    for (n = 0; n < SIZEOF(offsets); n++) {
	if (chksqr(prow + offsets[n].y, pcol + offsets[n].x)) {
	    cellmove(prow + offsets[n].y, pcol + offsets[n].x);
	    waddch(boardwin, mark);
	}
    }
}

static bool
find_next_move(int *y, int *x)
{
    unsigned j, k;
    int found = -1;
    int first = -1;
    int next = -1;
    int oldy, oldx;
    int newy, newx;
    bool result = FALSE;

    if (movecount > 1) {
	oldy = history[movecount - 1].y;
	oldx = history[movecount - 1].x;
	for (j = 0; j < SIZEOF(offsets) * 2; j++) {
	    k = j % SIZEOF(offsets);
	    newy = oldy + offsets[k].y;
	    newx = oldx + offsets[k].x;
	    if (chksqr(newy, newx)) {
		if (first < 0)
		    first = (int) k;
		if (newy == *y
		    && newx == *x) {
		    found = (int) k;
		} else if (found >= 0) {
		    next = (int) k;
		    break;
		}
	    }
	}
	if (found < 0)
	    next = first;
	if (next >= 0) {
	    *y = oldy + offsets[next].y;
	    *x = oldx + offsets[next].x;
	}
	result = TRUE;
    }
    return result;
}

static void
count_next_moves(int y, int x)
{
    int count = 0;
    unsigned j;

    wprintw(msgwin, "\nMove %d", movecount);
    for (j = 0; j < SIZEOF(offsets); j++) {
	int newy = y + offsets[j].y;
	int newx = x + offsets[j].x;
	if (chksqr(newy, newx)) {
	    ++count;
	}
    }
    wprintw(msgwin, ", gives %d choices", count);
    wclrtoeol(msgwin);
}

static void
unmarkcell(int row, int column)
{
    cellmove(row, column);
    waddch(boardwin, '\b');
    waddch(boardwin, ' ');
    waddch(boardwin, minus);
    waddch(boardwin, ' ');
}

static void
markcell(chtype tchar, int row, int column)
{
    cellmove(row, column);
    waddch(boardwin, '\b');
    waddch(boardwin, tchar);
    waddch(boardwin, tchar);
    waddch(boardwin, tchar);
}

static void
drawmove(chtype tchar, int oldy, int oldx, int row, int column)
/* place the stars, update board & currents */
{
    if (movecount <= 1) {
	int i, j;

	for (i = 0; i < BDEPTH; i++) {
	    for (j = 0; j < BWIDTH; j++) {
		if (movecount == 0) {
		    unmarkcell(i, j);
		} else {
		    cellmove(i, j);
		    if (winch(boardwin) == minus)
			waddch(boardwin, movecount ? ' ' : minus);
		}
	    }
	}
    } else {
	markcell(tchar, oldy, oldx);
	mark_possibles(oldy, oldx, ' ');
    }

    if (row >= 0 && column >= 0) {
	markcell(trail, row, column);
	mark_possibles(row, column, minus);
	board[row][column] = TRUE;
    }

    wprintw(msgwin, "\nMove %d", movecount);
    if (trialcount != movecount)
	wprintw(msgwin, " (%d tries)", trialcount);
    wclrtoeol(msgwin);
}

static int
iabs(int num)
{
    if (num < 0)
	return (-num);
    else
	return (num);
}

static bool
evalmove(int row, int column)
/* evaluate move */
{
    if (movecount == 1)
	return (TRUE);
    else if (board[row][column] == TRUE) {
	waddstr(msgwin, "\nYou've already been there.");
	return (FALSE);
    } else {
	int rdif = iabs(row - history[movecount - 1].y);
	int cdif = iabs(column - history[movecount - 1].x);

	if (!((rdif == 1) && (cdif == 2)) && !((rdif == 2) && (cdif == 1))) {
	    waddstr(msgwin, "\nThat's not a legal knight's move.");
	    return (FALSE);
	}
    }

    return (TRUE);
}

static int
completed(void)
{
    int i, j, count = 0;

    for (i = 0; i < BDEPTH; i++)
	for (j = 0; j < BWIDTH; j++)
	    if (board[i][j] != 0)
		count += 1;
    return (count == (BWIDTH * BDEPTH) ? -1 : count);
}

static void
no_previous_move(void)
{
    waddstr(msgwin, "\nNo previous move.");
    beep();
}

static void
play(void)
/* play the game */
{
    bool keyhelp;		/* TRUE if keystroke help is up */
    int i, j, count;
    int lastcol = 0;		/* last location visited */
    int lastrow = 0;
    int ny = 0, nx = 0;
    int review = 0;		/* review history */
    int rw = 0, col = 0;	/* current row and column */

    do {
	/* clear screen and draw board */
	werase(boardwin);
	werase(helpwin);
	werase(msgwin);
	dosquares();
	help1();
	wnoutrefresh(stdscr);
	wnoutrefresh(helpwin);
	wnoutrefresh(msgwin);
	wnoutrefresh(boardwin);
	doupdate();

	movecount = 0;
	for (i = 0; i < BDEPTH; i++) {
	    for (j = 0; j < BWIDTH; j++) {
		board[i][j] = FALSE;
		unmarkcell(i, j);
	    }
	}
	memset(history, 0, sizeof(history));
	history[0].y = history[0].x = -1;
	history[1].y = history[1].x = -1;
	lastrow = lastcol = -2;
	movecount = 1;
	trialcount = 1;
	keyhelp = FALSE;
	show_help(&keyhelp);

	for (;;) {
	    if (rw != lastrow || col != lastcol) {
		if (lastrow >= 0 && lastcol >= 0) {
		    cellmove(lastrow, lastcol);
		    if (board[lastrow][lastcol])
			waddch(boardwin, trail);
		    else
			waddch(boardwin, oldch);
		}

		cellmove(rw, col);
		oldch = winch(boardwin);

		lastrow = rw;
		lastcol = col;
	    }
	    cellmove(rw, col);
	    waddch(boardwin, plus);
	    cellmove(rw, col);

	    wrefresh(msgwin);

	    switch (wgetch(boardwin)) {
	    case 'k':
	    case '8':
	    case KEY_UP:
		ny = rw + BDEPTH - 1;
		nx = col;
		break;
	    case 'j':
	    case '2':
	    case KEY_DOWN:
		ny = rw + 1;
		nx = col;
		break;
	    case 'h':
	    case '4':
	    case KEY_LEFT:
		ny = rw;
		nx = col + BWIDTH - 1;
		break;
	    case 'l':
	    case '6':
	    case KEY_RIGHT:
		ny = rw;
		nx = col + 1;
		break;
	    case 'y':
	    case '7':
	    case KEY_A1:
		ny = rw + BDEPTH - 1;
		nx = col + BWIDTH - 1;
		break;
	    case 'b':
	    case '1':
	    case KEY_C1:
		ny = rw + 1;
		nx = col + BWIDTH - 1;
		break;
	    case 'u':
	    case '9':
	    case KEY_A3:
		ny = rw + BDEPTH - 1;
		nx = col + 1;
		break;
	    case 'n':
	    case '3':
	    case KEY_C3:
		ny = rw + 1;
		nx = col + 1;
		break;

#ifdef KEY_MOUSE
	    case KEY_MOUSE:
#ifdef NCURSES_MOUSE_VERSION
		{
		    MEVENT myevent;

		    getmouse(&myevent);
		    if (myevent.y >= CY(0) && myevent.y <= CY(BDEPTH)
			&& myevent.x >= CX(0) && myevent.x <= CX(BWIDTH)) {
			nx = CXINV(myevent.x);
			ny = CYINV(myevent.y);
			ungetch('\n');
			break;
		    } else {
			beep();
			continue;
		    }
		}
#endif /* NCURSES_MOUSE_VERSION */
#ifdef PDCURSES
		{
		    int test_y, test_x;
		    request_mouse_pos();
		    test_y = MOUSE_Y_POS + 0;
		    test_x = MOUSE_X_POS + 1;
		    if (test_y >= CY(0) && test_y <= CY(BDEPTH)
			&& test_x >= CX(0) && test_x <= CX(BWIDTH)) {
			ny = CYINV(test_y);
			nx = CXINV(test_x);
			wmove(helpwin, 0, 0);
			wrefresh(helpwin);
			ungetch('\n');
		    }
		    break;
		}
#endif /* PDCURSES */
#endif /* KEY_MOUSE */

	    case KEY_B2:
	    case '\n':
	    case ' ':
		review = 0;
		if (evalmove(rw, col)) {
		    drawmove(trail,
			     history[movecount - 1].y,
			     history[movecount - 1].x,
			     rw, col);
		    history[movecount].y = (short) rw;
		    history[movecount].x = (short) col;
		    movecount++;
		    trialcount++;

		    if (!chkmoves(rw, col)) {
			if (completed() < 0) {
			    waddstr(msgwin, "\nYou won.");
			} else {
			    waddstr(msgwin,
				    "\nNo further moves are possible.");
			}
		    }
		} else {
		    beep();
		}
		break;

	    case KEY_UNDO:
	    case KEY_BACKSPACE:
	    case '\b':
		review = 0;
		if (movecount <= 0) {
		    no_previous_move();
		} else if (movecount <= 1) {
		    ny = history[movecount].y;
		    nx = history[movecount].x;
		    if (nx < 0 || ny < 0) {
			ny = (lastrow >= 0) ? lastrow : 0;
			nx = (lastcol >= 0) ? lastcol : 0;
		    }
		    movecount = 0;
		    board[ny][nx] = FALSE;
		    oldch = minus;
		    drawmove(' ', ny, nx, -1, -1);
		    movecount = 1;
		    trialcount = 1;
		    no_previous_move();
		} else {
		    int oldy = history[movecount - 1].y;
		    int oldx = history[movecount - 1].x;

		    if (!board[rw][col]) {
			cellmove(rw, col);
			waddch(boardwin, ' ');
		    }

		    board[oldy][oldx] = FALSE;
		    --movecount;
		    ny = history[movecount - 1].y;
		    nx = history[movecount - 1].x;
		    if (nx < 0 || ny < 0) {
			ny = oldy;
			nx = oldx;
		    }
		    drawmove(' ', oldy, oldx, ny, nx);

		    /* avoid problems if we just changed the current cell */
		    cellmove(lastrow, lastcol);
		    oldch = winch(boardwin);
		}
		break;

	    case 'a':
		nx = col;
		ny = rw;
		if (find_next_move(&ny, &nx))
		    count_next_moves(ny, nx);
		else
		    beep();
		break;

	    case 'F':
		if (review > 0) {
		    review--;
		    ny = history[movecount - review - 1].y;
		    nx = history[movecount - review - 1].x;
		} else {
		    beep();
		}
		break;

	    case 'B':
		if (review < movecount - 2) {
		    review++;
		    ny = history[movecount - review - 1].y;
		    nx = history[movecount - review - 1].x;
		} else {
		    beep();
		}
		break;

	    case KEY_REDO:
	    case '\f':
	    case 'r':
		clearok(curscr, TRUE);
		wnoutrefresh(stdscr);
		wnoutrefresh(boardwin);
		wnoutrefresh(msgwin);
		wnoutrefresh(helpwin);
		doupdate();
		break;

	    case 'q':
	    case 'x':
		goto dropout;

	    case '?':
		show_help(&keyhelp);
		break;

	    default:
		beep();
		break;
	    }

	    col = nx % BWIDTH;
	    rw = ny % BDEPTH;
	}

      dropout:
	if ((count = completed()) < 0)
	    wprintw(msgwin, "\nYou won.  Care to try again? ");
	else
	    wprintw(msgwin, "\n%d squares filled.  Try again? ", count);
	wclrtoeol(msgwin);
    } while
	(tolower(wgetch(msgwin)) == 'y');
}

int
main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
{
    init_program();

    play();

    endwin();
    ExitProgram(EXIT_SUCCESS);
}

/* knight.c ends here */