Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > knight's tour helpppppp

Reply
Thread Tools

knight's tour helpppppp

 
 
whitehatmiracle@gmail.com
Guest
Posts: n/a
 
      01-27-2006
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[i];
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 == 1
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[i];
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[i][j]);
cout<<endl;
}
getch();

}

 
Reply With Quote
 
 
 
 
benben
Guest
Posts: n/a
 
      01-27-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> im stuck, thers a prob with the backtrack function.


What sort of a prob?

Ben
 
Reply With Quote
 
 
 
 
Heinz Ozwirk
Guest
Posts: n/a
 
      01-27-2006
<(E-Mail Removed)> schrieb im Newsbeitrag
news:(E-Mail Removed) oups.com...
> 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[i];
> 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


 
Reply With Quote
 
Gabriel
Guest
Posts: n/a
 
      01-27-2006
(E-Mail Removed) 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?
 
Reply With Quote
 
whitehatmiracle@gmail.com
Guest
Posts: n/a
 
      01-28-2006
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.

 
Reply With Quote
 
JustBoo
Guest
Posts: n/a
 
      01-28-2006
On 28 Jan 2006 02:47:31 -0800, "(E-Mail Removed)"
<(E-Mail Removed)> 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.
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      01-28-2006
JustBoo wrote:

> On 28 Jan 2006 02:47:31 -0800, "(E-Mail Removed)"
> <(E-Mail Removed)> 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:air< 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: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
 
Reply With Quote
 
whitehatmiracle@gmail.com
Guest
Posts: n/a
 
      01-30-2006
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

 
Reply With Quote
 
whitehatmiracle@gmail.com
Guest
Posts: n/a
 
      01-30-2006
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[i][j] = 100;
}
else
{
knight[i][0] = 100;
knight[i][1] = 100;
knight[i][max - 1] = 100;
knight[i][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 [i][j] != 100)
cout<< knight[i][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 [i][j] == (n - 1))
{
x = i; y = j;
n--;
i = max;
}
}
}

// choice++;
}

 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      01-30-2006
(E-Mail Removed) 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:air< 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Tour in Nepal, Nepal Tour, Nepal Tour Package tourinnepal Python 0 01-30-2010 09:53 AM
helpppppp!.SITES BLOCKED in .... xuxu Computer Security 0 02-17-2008 04:26 AM
ECS Production Tour 2005: How to build a mainboard Silverstrand Front Page News 1 06-26-2005 05:22 PM
how to transfer a programme to another computer HELPPPPPP beth Computer Support 10 04-03-2005 01:26 PM
Please helpppppp me on base64 Codec - jakarta jsp beginner Java 8 12-28-2004 11:05 PM



Advertisments