knight's tour helpppppp

[whitehatmiracle]

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 == 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[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",bo ard[i][j]);
cout<<endl;
}
getch();

}

[benben]

wh************* @gmail.com wrote:

im stuck, thers a prob with the backtrack function.

What sort of a prob?

Ben

[Heinz Ozwirk]

<wh************ *@gmail.com> schrieb im Newsbeitrag
news:11******** **************@ f14g2000cwb.goo glegroups.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

[Gabriel]

wh************* @gmail.com 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?

[whitehatmiracle]

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.

[JustBoo]

On 28 Jan 2006 02:47:31 -0800, "wh************ *@gmail.com"
<wh************ *@gmail.com> 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.

[Kai-Uwe Bux]

JustBoo wrote:

On 28 Jan 2006 02:47:31 -0800, "wh************ *@gmail.com"
<wh************ *@gmail.com> 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_invali d( Field const & f ) {
if ( ! ( f.first < BoardSize && f.second < BoardSize ) ) {
throw ( std::out_of_ran ge( "invalid field" ) );
}
}

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

bool & at ( Field const & f ) {
throw_if_invali d( 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.n um_queens() == configuration.s ize() ) {
throw ( configuration );
}
for ( unsigned row = 0; row < configuration.s ize(); ++row ) {
for ( unsigned col = 0; col < configuration.s ize(); ++col ) {
Field f ( row, col );
if ( ! configuration.i s_threatened( f ) ) {
Board new_conf ( configuration );
new_conf.put_qu een( f );
extend_partial_ solution( new_conf );
}
}
}
}

public:

static
Board solve ( void ) {
try {
extend_partial_ solution( Board() );
}
catch ( Board b ) {
return ( b );
}
throw ( std::logic_erro r( "no solution" ) );
}

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

Kai-Uwe Bux

[whitehatmiracle]

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

[whitehatmiracle]

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,tem p2, 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<<e ndl;
}
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++;
}

[Kai-Uwe Bux]

wh************* @gmail.com wrote:

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

[almost incomprehensibl e 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.inser t( 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*Board Size );
}

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().bac k().
For each hit, extend the route by that field (and then recurse).
Hope this gets you started

Best

Kai-Uwe Bux