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;
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();

}

 

[benben]

im stuck, thers a prob with the backtrack function.

What sort of a prob?

Ben

 

[Heinz Ozwirk]

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];

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

 

[Gabriel]

(e-mail address 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.

 

[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]

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]

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

 

[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,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++;
}

 

[Kai-Uwe Bux]

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