473,379 Members | 1,278 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,379 software developers and data experts.

knight's tour helpppppp

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

}

Jan 27 '06 #1
9 4599
wh*************@gmail.com wrote:
im stuck, thers a prob with the backtrack function.


What sort of a prob?

Ben
Jan 27 '06 #2
<wh*************@gmail.com> schrieb im Newsbeitrag
news:11**********************@f14g2000cwb.googlegr 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
Jan 27 '06 #3
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?
Jan 27 '06 #4
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 '06 #5
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.
Jan 28 '06 #6
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_invalid( Field const & f ) {
if ( ! ( f.first < BoardSize && f.second < BoardSize ) ) {
throw ( std::out_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
Jan 28 '06 #7
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 '06 #8
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++;
}

Jan 30 '06 #9
wh*************@gmail.com 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
Jan 30 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
by: googlegroups111 | last post by:
This is an EXCERPT from the story of the Philip Bartlett the Knight in Shining Armour from the days of hoary olde England, a story adapted by an author who shall remain nameless..... One day...
3
by: Ekhaat | last post by:
Hi I followed the Web Matrix guided tour and came to the "ASP.NET Pages with Data (Microsoft Access)" part. There is really not much you can do wrong there, but for some reason, the INSERT...
0
by: James | last post by:
I've tried an XML service in a VB.NET Guided Tour sample. In Step 6-5, I couldn't create a new category called "TaskManagement" in the "Performance Counter" path. It doesn't show...
4
by: Xah Lee | last post by:
A Lambda Logo Tour (and why LISP languages using λ as logo should not be looked upon kindly) Xah Lee, 2002-02 Dear lispers, The lambda character λ, always struck a awe in me, as with...
17
by: foahchon | last post by:
Hi, I'm trying to write a program to solve (or whatever) the Knight's Tour. I know this is a pretty common problem, but I haven't found a solution that I can really compare mine to and isolate what...
18
by: Bert | last post by:
This is a past question from a programming competition. On a chess board (8 squares by 8 squares), there's is a knight sitting on b1 (2 from the left of the bottom row). To cut the crap, find out...
3
by: sliever | last post by:
hey! to anyone out there who might be able to help me with my problem about the knight's tour using php pls. help me.. i've come up with a long solution... ?> $chessboard=array ( ...
0
by: slapsh0t11 | last post by:
Hello, I know this is a popular problem with a lot of solutions, but I don't want to be pointed to a post by someone else with THEIR solution. I want to figure out how to make my own code work. ...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.