/* In my investigation of simple compilers I found it necessary to fully
understand recursive backtracking algorithms, since block structured
language is recursive by nature, many a compiler was based on the Recursive
Descent Parser, a kind of recursive backtracking algorithm.  This program
was translated from pseudo pascal from a book by Nicklaus Wirth called
Algorithms + Data Structures = Programs.
Ok class turn to page 137 and read the section on Backtracking algorithms
in it you will find the Knights Tour problem, the rules are simple start
somewhere on somesize chess board and use the Knight to touch every square on
the board, but touch it only once.  This is non-trivial for a human with their
Be-gillion or so neurons.  So howza poor non-mortal lowly computer supoz'ta
do it...

Note: Compile this program under Mix Power C and then trace it, one very
interesting thing to do is to step through until you get into the funct try()
then set trace to display the variables window to the whole screen and move
into the variables such that as much of the h[] array is visible as possible.
This will allow you to see the effect of recursing down dead end streets, and
of subsequent backtracking recursing again.  Have fun...

ÚÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄ¿   From a given position on a chess board the Knight
³    ³ 2  ³    ³ 1  ³    ³   has 8 legal moves, I've numbered them here 0 - 7.
ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´   If you view the Knight as the center of the
³ 3  ³    ³    ³    ³ 0  ³   universe, or at least the origin of the cartesian
ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´   coordinate plane, legal move 0 has an X value of
³    ³    ³KNT ³    ³    ³   positive 2 and a Y value of positive 1, another
ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´   example move 5 has an X value of negative 1 and
³ 4  ³    ³    ³    ³ 7  ³   a Y value of negative 2.
ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´   The following two dimention constant array is
³    ³ 5  ³    ³ 6  ³    ³   framed as array_name[coordinate][move]
ÀÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÙ   Where: array_name = lgl
                                    coordinate = X is 0 or Y is 1
                                    move = 0 - 7
*/
const int lgl[2][8]={2,1,-1,-2,-2,-1,1,2,1,2,2,1,-1,-2,-2,-1};

int n, nsq;
int i, j, q;
int h[401]; /* a two dimentioned array n by n where n is known at runtime */

main()
{
printf("Enter length of chess board -->");
scanf("%d", &n);
nsq = n * n; /* number squared */
if (nsq > 400)
    {
    printf("Sorry chess board larger than 20 x 20\n");
    return;
    }
for (i=0; i<n; i++)
    for (j=0; j<n; j++)
        h[(i * n) + j] = 0; /* initalize the two dimention array to zero */
h[0] = 1;/* Seed location x,y = 0,0 = h[0][0] = h[(0 * n) + 0)] to be origin */
try(2, 0, 0, &q); /* Start recursion looking for Square 2 from x,y = 0,0 */
if (q)
    {
    for (i=0; i<n; i++)
        {
        for (j=0; j<n; j++)
            /* draw chess board with Knight move sequence */
            printf("%2d   ", h[(i * n) + j]);
        printf("\n");
        }
    } else
    {
    printf("No Solution\n");
    }
}


try(i, x, y, q)
int i, x, y, *q;
    {
    int k, u, v, ql;
    k = -1;
    do  {
        k++; /* Test the next in the list possible moves a knight can make */
        ql = 0; /* set to false */
        u = x + lgl[1][k];
        v = y + lgl[0][k]; /* here u & v assume that position */
        if (u>=0 && u<n && v>=0 && v<n) /* u & v test if knight is on board */
            {
            if (h[(u * n) + v] == 0) /* test if board position is virgin */
                {
                h[(u * n) + v] = i; /* Lay sequence number tile down on board */
                if (i < nsq) /* is there more work to be done */
                    {
                    try(i + 1, u, v, &ql); /* try to solve rest by recursion */
/* above this line we'er recursing inward passing on the next tile (i + 1)  */
/* to be tested, also passing the current x,y (u,v) coordinate and the      */
/* address of the current local True/False variable (&ql).  Until (&ql) is  */
/* affected by the many depths of recursion we know not, whither the tile   */
/* we laid down will end up painting us into a corner and thus that tile    */
/* must be removed or whither we can cement it in place confident a solution*/
/* is possible with that position of the chessboard taken by the i'th tile. */
/* -  -  -  -  -  -  -  -  - */
/* Below this line we are unwinding the depths of recursion.  If ql is true */
/* I.E. a solution is found the tile (sequence number) stays stuck.  However*/
/* if ql comes back false we must rip the tile back up, clean the cement off*/
/* that square of the board thus restoring it's virginity, once thats done  */
/* watch what happends if the knight hasen't tried all of his tricks from   */
/* this level I.E. (k < 7) it will recurse deeper laying down yet another   */
/* tile onto the board.                                                     */
                    if (ql == 0) h[(u * n) + v] = 0; /* No? restore virginity */
                    }else
                    {
                    /* if we're at the end prepare for a successfull unwind */
                    ql = -1;
                    }
                }
            }
        } while (ql == 0 && k < 7);
    *q = ql;
    }