knight's tour helpppppp

Discussion in 'C++' started by whitehatmiracle@gmail.com, Jan 27, 2006.

  1. Guest

    im stuck, thers a prob with the backtrack function.

    #include <iostream.h>
    #include <conio.h>
    #include <stdio.h>
    #include <string.h>
    #include <ctype.h>
    #include <stdlib.h>
    #define size 5

    void move();
    void printBoard();
    int checkMove();
    void backtrack();
    int board[5][5];
    int x,y, tempx, tempy,markx=-1, marky=-1, a,step =1, row, col, flag,
    chk_move;
    int l[8] = {-2,-2,-1,-1,1,1,2,2};
    int m[8] = {-1,1,-2,2,-2,2,-1,1};


    int main()
    {
    clrscr();
    x=0; y=0;
    cout<<"Press any key to see the knight's moves to cover a whole chess
    board\n";

    board[x][y]=1;
    move();


    printBoard();
    getch();
    return 0;
    }

    void move()
    {
    int t=0;
    while (step!=25){ /////////////////squares
    flag = step;
    for (int i=0, j =0; i<8, j<8; i++, j++){
    tempx= x + l;
    tempy= y + m[j];
    if ( ((tempx < size) && (tempx >= 0) && (tempy < size) && (tempy >= 0)
    )
    && (board[tempx][tempy] == 0 ) ) { /////// move validity check
    x=tempx;
    y=tempy;;
    step++;
    board[x][y]=step;
    board[markx][marky]=0;
    t=1;
    // printBoard();
    // getch();

    if (step == 18)
    getch();
    move();

    }
    }
    if (flag==step){
    if (t==0)
    board[markx][marky]=0;

    markx=x;
    marky=y;
    backtrack();
    }

    }//while
    }


    void backtrack()
    {

    // board[x][y]=0; // no steps possible, ini current position

    for (int i=0, j =0; i<8, j<8; i++, j++){
    tempx= x + l;
    tempy= y + m[j];
    if ( ((tempx < size) && (tempx >= 0) && (tempy < size) && (tempy >= 0)
    )
    && (board[tempx][tempy] == step-1 ) ) { /////// move validity check
    x=tempx;
    y=tempy;;
    step--;
    board[x][y]=step;

    break;
    }
    // break;
    }
    // move();
    }



    void printBoard()
    {
    clrscr();
    cout<<endl;
    for (int i=0; i<5;i++){
    for (int j=0;j<5;j++)
    printf("%5d",board[j]);
    cout<<endl;
    }
    getch();

    }
     
    , Jan 27, 2006
    #1
    1. Advertising

  2. benben Guest

    wrote:
    > im stuck, thers a prob with the backtrack function.


    What sort of a prob?

    Ben
     
    benben, Jan 27, 2006
    #2
    1. Advertising

  3. Heinz Ozwirk Guest

    <> schrieb im Newsbeitrag
    news:...
    > im stuck, thers a prob with the backtrack function.
    >
    > #include <iostream.h>


    There is no such header (any more). Use <iostream> instead.

    > #include <conio.h>
    > #include <stdio.h>
    > #include <string.h>
    > #include <ctype.h>
    > #include <stdlib.h>
    > #define size 5
    >
    > void move();
    > void printBoard();
    > int checkMove();
    > void backtrack();
    > int board[5][5];


    Why did you define size if you don't use it?

    > int x,y, tempx, tempy,markx=-1, marky=-1, a,step =1, row, col, flag,
    > chk_move;
    > int l[8] = {-2,-2,-1,-1,1,1,2,2};
    > int m[8] = {-1,1,-2,2,-2,2,-1,1};


    It would be better to replace these two arrays with one single array of
    structs:

    struct
    {
    int dx;
    int dy;
    } distance[] = {{-2, -1},{-2, 1},...};
    >
    >
    > int main()
    > {
    > clrscr();
    > x=0; y=0;
    > cout<<"Press any key to see the knight's moves to cover a whole chess
    > board\n";
    >
    > board[x][y]=1;
    > move();
    >
    >
    > printBoard();
    > getch();
    > return 0;
    > }
    >
    > void move()
    > {
    > int t=0;
    > while (step!=25){ /////////////////squares
    > flag = step;
    > for (int i=0, j =0; i<8, j<8; i++, j++){


    Why are you using to different variables that always have the same value?

    > tempx= x + l;
    > tempy= y + m[j];
    > if ( ((tempx < size) && (tempx >= 0) && (tempy < size) && (tempy >= 0)
    > )
    > && (board[tempx][tempy] == 0 ) ) { /////// move validity check
    > x=tempx;
    > y=tempy;;
    > step++;
    > board[x][y]=step;
    > board[markx][marky]=0;


    When the program comes here for the first time, markx and marky are both
    less than zero. This is undefined behaviour and anything may happen from now
    on.

    HTH
    Heinz
     
    Heinz Ozwirk, Jan 27, 2006
    #3
  4. Gabriel Guest

    wrote:

    <lots of stuff you might do in C>

    I see this so often in this newsgroup. People keep using C-style arrays
    and are later surprised why things get difficult. C-style arrays are
    an expert feature to perform special tasks:
    - calling some C APIs (though the most you can still beat with std::vector)
    - performing some high-end optimizations
    - nothing else that I can think of right now.
    Don't.

    Decide wether you want to use C or C++, but be aware that they differ
    very much. If you use C++, use the STL containers.

    --
    Who is General Failure and why is he reading my hard disk?
     
    Gabriel, Jan 27, 2006
    #4
  5. Guest

    Actually the program is running till 19 steps. Then it backtracks till
    the 16th step. And then is stuck forever.

    So i dont know how to go about storing the moves in a an array, so that
    the backtrack function can start its next search from that particualr
    move.
     
    , Jan 28, 2006
    #5
  6. JustBoo Guest

    On 28 Jan 2006 02:47:31 -0800, ""
    <> wrote:
    >Actually the program is running till 19 steps. Then it backtracks till
    >the 16th step. And then is stuck forever.
    >
    >So i dont know how to go about storing the moves in a an array, so that
    >the backtrack function can start its next search from that particualr
    >move.


    Would the Command Pattern or the Memento Pattern be of use in this
    case? They are in the Design Patterns book.
     
    JustBoo, Jan 28, 2006
    #6
  7. Kai-Uwe Bux Guest

    JustBoo wrote:

    > On 28 Jan 2006 02:47:31 -0800, ""
    > <> wrote:
    >>Actually the program is running till 19 steps. Then it backtracks till
    >>the 16th step. And then is stuck forever.
    >>
    >>So i dont know how to go about storing the moves in a an array, so that
    >>the backtrack function can start its next search from that particualr
    >>move.

    >
    > Would the Command Pattern or the Memento Pattern be of use in this
    > case? They are in the Design Patterns book.



    Sounds interesting. I read a lot about patterns in this group, but I have
    never gotten into any of those books that everybody else seems to absorb at
    amazing speed. Programming is just a past time activity to me, so the
    amount of reading I spend on it is limited.

    Anyway, this sounds like an interesting test case since the complexity is
    not to high although the problem is non-trivial. Since the knights tour
    sound like a homework problem, let's consider the problem of placing 8
    queens on the chess board so that they do not threaten one another.

    Here is the straight forward solution just using recursion to extend a
    partial solution. I would love to see a pattern oriented approach for
    comparison.


    #include <iostream>
    #include <stdexcept>

    template < unsigned BoardSize >
    struct Board {

    typedef std::pair< unsigned, unsigned > Field;

    static
    bool are_threatening ( Field const a, Field const & b ) {
    if ( a.first == b.first ) { return ( true ); }
    if ( a.second == b.second ) { return ( true ); }
    if ( a.second - b.second == a.first - b.first ) { return ( true ); }
    if ( a.second - b.second == b.first - a.first ) { return ( true ); }
    return ( false );
    }

    private:

    bool data [BoardSize][BoardSize];

    unsigned num;

    static
    void throw_if_invalid( Field const & f ) {
    if ( ! ( f.first < BoardSize && f.second < BoardSize ) ) {
    throw ( std::eek:ut_of_range( "invalid field" ) );
    }
    }

    bool const & at ( Field const & f ) const {
    throw_if_invalid( f );
    return ( this->data[f.first][f.second] );
    }

    bool & at ( Field const & f ) {
    throw_if_invalid( f );
    return ( this->data[f.first][f.second] );
    }

    public:

    Board ( void )
    : data ()
    , num ( 0 )
    {}

    void put_queen ( Field const & f ) {
    if ( ! this->at(f) ) {
    this->at(f) = true;
    ++ this->num;
    }
    }

    bool has_queen ( Field const & f ) const {
    return( this->at(f) );
    }

    unsigned num_queens ( void ) const {
    return ( this->num );
    }

    unsigned size ( void ) const {
    return( BoardSize );
    }

    void print ( void ) const {
    for ( unsigned row = 0; row < BoardSize; ++row ) {
    for ( unsigned col = 0; col <BoardSize; ++col ) {
    if ( this->has_queen( Field( row, col ) ) ) {
    std::cout << row << " " << col << "\n";
    }
    }
    }
    }

    bool is_threatened ( Field const & f ) const {
    for ( unsigned row = 0; row < BoardSize; ++row ) {
    for ( unsigned col = 0; col <BoardSize; ++col ) {
    Field g ( row, col );
    if ( has_queen( g ) && are_threatening( f, g ) ) {
    return ( true );
    }
    }
    }
    return ( false );
    }

    private:

    static
    void extend_partial_solution ( Board const & configuration ) {
    if ( configuration.num_queens() == configuration.size() ) {
    throw ( configuration );
    }
    for ( unsigned row = 0; row < configuration.size(); ++row ) {
    for ( unsigned col = 0; col < configuration.size(); ++col ) {
    Field f ( row, col );
    if ( ! configuration.is_threatened( f ) ) {
    Board new_conf ( configuration );
    new_conf.put_queen( f );
    extend_partial_solution( new_conf );
    }
    }
    }
    }

    public:

    static
    Board solve ( void ) {
    try {
    extend_partial_solution( Board() );
    }
    catch ( Board b ) {
    return ( b );
    }
    throw ( std::logic_error( "no solution" ) );
    }

    };


    int main ( void ) {
    Board<8>::solve().print();
    }


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Jan 28, 2006
    #7
  8. Guest

    Thats kewl, interesting. I had an option to choose from the queens
    problem and the knight.

    Hmmmmm should have chosen the queeeens. LOL
    NIce!111
     
    , Jan 30, 2006
    #8
  9. Guest

    I got a similar code for the knight's tour, cant figure out the
    choice_monitor's function..
    HELP

    #include <iostream.h>
    #include <conio.h>
    #include <time.h>
    #include <stdlib.h>
    #define max 9




    void do_knight();
    void print_knight();
    void search_previous();

    int knight[max][max], movechoice[25], movechoice2[25];
    int x = 2 , y = 2, n = 1, choice,temp,temp2, tempx, tempy,
    prevn1,prevn2;
    int choice_moniter = 0;

    main()
    {
    knight[y][x] = 1;
    clrscr();
    // fill the borders with some junk
    for (int i = 0; i < max; i++)
    {
    if ((i == 0) || (i == 1) || (i == (max - 2)) || (i == (max - 1)))
    {
    for (int j = 0; j < max; j++)
    knight[j] = 100;
    }
    else
    {
    knight[0] = 100;
    knight[1] = 100;
    knight[max - 1] = 100;
    knight[max - 2] = 100;
    }
    }
    print_knight();
    do_knight();
    getch();
    return 0;
    }

    void print_knight()
    {

    int ch;
    clrscr();
    for (int i = 0; i < max; i++)
    {
    cout<<" ";
    for (int j = 0; j < max; j++)
    {
    if (knight [j] != 100)
    cout<< knight[j]<<" ";
    }
    cout <<endl<<endl<<endl;
    }
    ch = getch();
    // if (ch == 27)
    // exit(1);


    }


    void do_knight()
    {

    if ((knight[x - 1][y-2]) && (knight[x - 1][y+2])
    && (knight[x - 2][y-1])&& (knight[x - 2][y+1])
    && (knight[x + 1][y-2])&& (knight[x + 1][y+2])
    && (knight[x + 2][y-1])&& (knight[x + 2][y+1]))
    {

    search_previous();
    print_knight();
    choice ++;
    do_knight();

    }
    else
    {
    temp = n;
    if (choice > 7)
    choice = 0;
    while(temp == n)

    {
    // randomize();
    // choice = rand() % 8;
    if (choice > 7)
    choice = 0;
    // cout<<choice;

    switch(choice)
    {
    case 0: if (knight[x - 2][y-1])
    break;
    else
    {
    n++;
    knight[x-2][y-1] = n;
    x-=2;
    y-=1;
    }
    break;
    case 1: if (knight[x - 2][y+1])
    break;
    else
    {
    n++;
    x-=2;
    y+=1;
    knight[x][y] = n;
    }break;
    case 2: if (knight[x - 1][y-2])
    break;
    else
    {
    n++;
    x-=1;
    y-=2;
    knight[x][y] = n;
    }break;
    case 3: if (knight[x - 1][y+2])
    break;
    else
    {
    n++;
    x-=1;
    y+=2;
    knight[x][y] = n;
    }break;
    case 4: if (knight[x + 1][y-2])
    break;
    else
    {
    n++;
    x+=1;
    y-=2;
    knight[x][y] = n;
    }break;
    case 5: if (knight[x +1][y+2])
    break;
    else
    {
    n++;
    x+=1;
    y+=2;
    knight[x][y] = n;
    }break;
    case 6: if (knight[x +2 ][y-1])
    break;
    else
    {
    n++;
    x+=2;
    y-=1;
    knight[x][y] = n;
    }break;
    case 7: if (knight[x + 2][y+1])
    break;
    else
    {
    n++;
    x+=2;
    y+=1;
    knight[x][y] = n;
    }break;
    }//switch

    choice++;
    }//while
    if (movechoice[n] == choice) //see if choice has come before
    {
    search_previous();
    search_previous();
    movechoice[n+2] = 0;
    }
    else
    {
    if ((movechoice2[n] == choice) && (movechoice2[n] !=
    movechoice[n]))//see if second choice has come before
    {
    search_previous();
    search_previous();
    movechoice2[n+2] = 0;

    }
    else
    {
    if (choice_moniter) // alternate the alloting of choice(put choice
    in array 1 and next time in 2
    movechoice2[n] = choice;
    else
    movechoice[n] = choice;
    choice_moniter = !choice_moniter;
    }
    }
    print_knight();
    if (n != 25)
    do_knight();
    else
    exit(1);
    }//else

    }

    void search_previous()
    {
    /*
    if ((temp2 == n) && (tempx == x) && (tempy == y))
    search_previous();
    else
    tempx = x; tempy = y; temp2 = n;
    */
    knight[x][y] = 0;
    for (int i = 2; i < (max - 2); i++)
    {
    for (int j = 2; j < (max - 2); j++)
    {
    if (knight [j] == (n - 1))
    {
    x = i; y = j;
    n--;
    i = max;
    }
    }
    }

    // choice++;
    }
     
    , Jan 30, 2006
    #9
  10. Kai-Uwe Bux Guest

    wrote:

    > I got a similar code for the knight's tour, cant figure out the
    > choice_monitor's function..
    > HELP

    [almost incomprehensible C code snipped]

    Well, I have no idea about that code. But I recommend you start thinking
    about programming the C++ way, i.e., find the right abstractions use them
    to design classes. For the knight's tour, the idea is to construct a route
    by adding field after field to some partial solution. Here is one way to
    put that into a class:


    typedef std::pair< unsigned, unsigned > Field;

    class KnightsTour {

    unsigned BoardSize;
    std::set< Field > unvisited;
    std::vector< Field > route;

    public:

    KnightsTour ( unsigned board_size )
    : BoardSize ( board_size )
    , unvisited ()
    , route ()
    {
    for ( unsigned row = 0; row < BoardSize; ++row ) {
    for ( unsigned col = 0; col < BoardSize; ++col ) {
    unvisited.insert( Field( row, col ) );
    }
    }
    }

    KnightsTour ( KnightsTour const & other )
    : BoardSize ( other.BoardSize )
    , unvisited ( other.unvisited )
    , route ( other.route )
    {}

    KnightsTour & operator= ( KnightsTour const & other ) {
    BoardSize = other.BoardSize;
    unvisited = other.unvisited;
    route = other.route;
    return ( *this );
    }

    std::set< Field > const & get_unvisited ( void ) const {
    return ( unvisited );
    }

    std::vector< Field > const & get_route ( void ) const {
    return ( route );
    }

    void append_field_to_route ( Field const & f ) {
    assert( f.first < BoardSize && f.second < BoardSize );
    assert( unvisited.find( f ) != unvisited.end() );
    unvisited.erase( f );
    route.push_back( f );
    }

    bool is_solution ( void ) const {
    return ( route.size() == BoardSize*BoardSize );
    }

    unsigned get_board_size ( void ) const {
    return ( BoardSize );
    }

    }; // KnightsTour


    Now, try to find a recursive algorithm that only uses these primitives to
    construct a solution using recursion to do the backtracking. Start with
    asking which additional functions you will need, e.g.:

    a) You will need a function that decides whether to fields are a knight's
    move apart.

    b) You will need a function that tries to extend a given tour by one field.
    To this end, it will iterate through the get_unvisited() fields and check
    all of those wether they are a knight's move away from get_route().back().
    For each hit, extend the route by that field (and then recurse).


    Hope this gets you started

    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Jan 30, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jsp beginner
    Replies:
    8
    Views:
    3,502
    Tris Orendorff
    Dec 28, 2004
  2. tourinnepal
    Replies:
    0
    Views:
    286
    tourinnepal
    Jan 30, 2010
  3. Robin Rytich
    Replies:
    0
    Views:
    710
    Robin Rytich
    Mar 10, 2010
  4. Gabriel Genellina

    Knight's tour Warndorff's algorithm problem

    Gabriel Genellina, Mar 10, 2010, in forum: Python
    Replies:
    4
    Views:
    1,135
    Terry Reedy
    Mar 11, 2010
  5. Walter Roberson

    Knight's tour in perl ithreads

    Walter Roberson, Feb 2, 2004, in forum: Perl Misc
    Replies:
    0
    Views:
    135
    Walter Roberson
    Feb 2, 2004
Loading...

Share This Page