Knight movement.... " how to output all possible moves. "

Question

The following is the code i wrote.. I have to write it for nXn but for easyness i tried to test it for 5X5. It does not display my output... could anybody tell me whats wrong with the following code:

{ 
#include <iostream>
#include <iomanip>

using namespace std;

void knight ( int startx, int starty, int n, int p[][5], int used [][5], int &count);

int main ( )
{
    const int n = 5; // no. of cloumns and rows
    int startx = 0;
    int starty = 0;
    int p[5][5];
    int used[5][5];
    int count = 1;

    int i= 0;
    int j = 0;

    //initializing the array
    for ( i = 0; i < 5; i++)
    {
        for ( j = 0; j < 5; j++)
        {
            p[i][j] = 0;
            used [i][j] = 0;
        }
    }

    //outputting the initialized array.. 
        i=0;
        while ( i< 5)
        {
            for ( j = 0; j < 5; j++)
            {
                cout << setw(3) << p[i][j];             
            }
            i++;
            cout << endl;
        }
        knight (startx,starty,n,p,used,count);

    return 0;
}

void knight ( int x, int y, int n, int p[][5], int used [][5], int &count)
{

        int i = 0;

    //knight (x,y,n,p,used,count)
    for ( i = 0; i < n*n; i++)
    {
        if ( used [x][y] == 0 )
        {
            used[x][y] = 1; // mark it used;
            p[x][y] += count; //inserting step no. into the solution

            //go for the next possible steps;

            //move 1
            //2 squares up and 1 to the left
            if (x-1 < 0 && y+2 < n && p[x-1][y+2] == 0)
            {   
                used[x-1][y+2] = 1;
                p[x-1][y+2] += count;
                knight (x-1,y+2,n,p,used,count);
                used[x-1][y+2] = 0;
            }

            //move 2
            //2 squares up and 1 to the right
            if ( x+1 < n && y+2 < n && p[x+1][y+2] == 0 )
            {
                used[x+1][y+2] = 1;
                p[x+1][y+2] += count;
                knight (x+1,y+2,n,p,used,count);
                used[x+1][y+2] = 0;
            }

            //move 3
            //1 square up and 2 to the right
            if ( x+2 < n && y+1 < n && p[x+2][y+1] == 0 )
            {
                used[x+2][y+1] = 1;
                p[x+2][y+1] += count;
                knight (x+2,y+1,n,p,used,count);
                used[x+2][y+1] = 0;
            }

            //move 4
            //1 square down and 2 to the right
            if ( x+2 < n && y-1 < n && p[x+2][y-1] == 0 )
            {
                used[x+2][y-1] = 1;
                p[x+2][y-1] += count;
                knight (x+2,y-1,n,p,used,count);
                used[x+2][y-1] = 0;
            }

            //move 5
            //2 squares down and 1 to the right
            if ( x+1 < n && y-2 < n && p[x+1][y-2] == 0 )
            {
                used[x+1][y-2] = 1;
                p[x+1][y-2] += count;
                knight (x+1,y-2,n,p,used,count);
                used[x+1][y-2] = 0;
            }

            //move 6
            //2 squares down and 1 to the left
            if ( x-1 < n && y-2 < n && p[x-1][y-2] == 0 )
            {
                used[x-1][y-2] = 1;
                p[x-1][y-2] += count;
                knight (x-1,y-2,n,p,used,count);
                used[x-1][y-2] = 0;
            }

            //move 7
            //1 square down and 2 to the left
            if ( x-2 < n && y-1 < n && p[x-2][y-1] == 0 )
            {
                used[x-2][y-1] = 1;
                p[x-2][y-1] += count;
                knight (x-2,y-1,n,p,used,count);
                used[x-2][y-1] = 0;
            }

            //move 8
            //one square up and 2 to the left
            if ( x-2 < n && y+1< n && p[x-2][y+1] == 0 )
            {
                used[x-2][y+1] = 1;
                p[x-2][y+1] += count;
                knight (x-2,y+1,n,p,used,count);
                used[x-2][y+1] = 0;
            }
        }
    }

    if ( x == n-1 && y == n-1)
    {
        while ( i != n)
        {
            for ( int j = 0; j < n; j++)
                cout << setw(3) << p[i][j];
            i++;
        }
    }
}

Thank you!!

Answer 1

First off, some compilers are picky and will give you a warning if the variable names are different in your function declarations and definitions.

void knight ( int startx, int starty, int n, int p[][5], int used [][5], int &count);
[...]
void knight ( int x, int y, int n, int p[][5], int used [][5], int &count) { ... }

Second, if you are trying to pass an int pointer into knight (parameter count) then you would use int *count. If you're going to be using recursion in knight, you might be better off either declaring count as a global, or (as it looks like here) if the count parameter is only valid for that particular call tree, you may want to not use a pointer, and just give each call its own count.

Third, what is with the rogue { at the top of the file? Did you mean to put that there?

What does the program do when you run it? Have you tried inserting debugging messages that print out in various parts of the code so that you can see where errors or infinite loops occur?

Answer 2

These are all hints at different problems in your code:

At the point of your program where if ( x == n-1 && y == n-1) executes, what value does i have? How does it get that value?

What effect does this loop for ( i = 0; i < n*n; i++) actually have?

When you have an expression like y-2 < n is that really what you want? Can y-2 ever not be less than n?

Answer 3

i got the answer. thank you for looking out my concern... the ans is as follows:

#include <iostream>
#include <iomanip>

using namespace std;

bool move(int *p[] ,int x, int y,int n);
void knights (int *p[],int x,int y,int n, int count, int &pmt);
void output(int *p[],int n);

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

    int count = 1;
    int pmt = 0;
    int n;  //for size of board
    int x,y; // starting pos
    int **p; // to hold no. of combinations

    if ( argc != 4)
    {
        cout << "Very few arguments. Please try again.";
        cout << endl;
            return 0;
    }

    n = atoi(argv[1]);
    if( argv[1] <= 0 )
    {
        cout << " Invalid board size. ";
        return 0;
    }

    x = atoi(argv[2]);
    y = atoi(argv[3]);

    cout << "board size: " << n << ", "<< n << endl;
    cout << "starting pos: " << x << ", " << y << endl;


    //dynamic allocation of arrays to hold permutation
    p = new int *[n];
    for (int i = 0; i < n; i++)
        p[i] = new int [n];    

    //initializing board
    int i, j;
    for (i=0; i<n; i++)
    {
        for (j=0; j<n; j++)
        {
            p[i][j] = 0;
        }
    }

    output(p,n); // check output format
    knights(p,x,y,n,count,pmt);
    cout << "no. perm " << pmt << endl;


    return 0;
}

void output(int *p[],int n)
{
    int i = 0;
    int j;

    while ( i != n)
    {
        for ( j=0; j<n; j++)
        {
            cout << setw(10) << p[i][j];
        }
        cout << endl;
        i++;
    }
}

bool move(int *p[],int x, int y,int n)
{

    if (x < 0 || x >= n)
    {
        return false;
    }
    if ( y < 0 || y >= n)
    {
        return false;
    }

    if( p[x][y] != 0 )
    {
        return false;
    }

    return true;
}

void knights (int *p[], int x,int y,int n ,int count , int &pmt)
{    
    if(!move(p,x,y,n))
    {
        return;
    }

    if (count == n*n)    
    {
        cout << "New solution found: " << endl <<endl;
        p[x][y]=count;
        output(p,n);
        p[x][y]= 0;
        pmt++;
    }

    if ( p[x][y] == 0 )
    {
        p[x][y] = count;

        //move 1
        knights (p,  x-1, y-2, n, count+1, pmt);

        //move 2
        knights (p,  x+1, y-2, n, count+1, pmt);

        //move 3
        knights (p,  x+2, y-1, n, count+1, pmt);

        //move 4
        knights (p,  x+2, y+1, n, count+1, pmt);

        //move 5
        knights (p,  x+1, y+2, n, count+1, pmt);

        //move 6
        knights (p,  x-1, y+2, n, count+1, pmt);

        //move 7
        knights (p,  x-2, y+1, n, count+1, pmt);

        //move 8
        knights (p,  x-2, y-1, n, count+1, pmt);

        p[x][y] = 0; //setting square back to zero
    }        
}