9 Replies - 510 Views - Last Post: 06 November 2018 - 05:31 AM Rate Topic: -----

#1 Kintana   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 30-October 18

Stack and Knight Tour

Posted 05 November 2018 - 02:40 AM

I'm learning about stack and I find some code about the knight tour but I don't know something about the retract_move function. So I need someone explained for why they use mtype =(move_type+4)%8 in them code.
//	Knight's tour on a 6 x 6 board using stack 1

#include <iostream>
using namespace std;

#include <ctime>

#define N 6
#define STMAX N*N

int     stack[STMAX];
int     stp = 0;

void push(int v){
	stack[stp++] = v;
}

int pop(){
	return stack[--stp];
}

int top(){
	return stack[stp-1];
}

int stack_empty(){
	return stp == 0;
}

int stack_full(){
	return stp == STMAX;
}

int     board[N][N];
int     x,
        y,
        newx,
        newy,
        move_number,
        move_type;

void main () {
	int p=0;
	unsigned long t;
	double time;

    int  move_valid ();
    void print_board();
    void retract_move ();
    void try_move (int);

	void push(int v);
	int pop();
	int stack_empty();

    board[0][0] = 1;

    move_number = 2;
    move_type = 0;
    newx = x = 0;
    newy = y = 0;

//  insert prior to the code you want to time
	t = clock();

    do {

    	do {
			while (move_type == 8) {
			retract_move ();
			}
			move_type++;
			try_move (move_type);
		} while (!move_valid ());

		p++;
		push (move_type);
		x = newx;
		y = newy;
		move_type = 0;
		board[x][y] = move_number++;
		if(move_number> N*N) 
			print_board();
    } while (move_number <= N*N);

//  insert after to the code you want to time
  	time = ((double)(clock() - t)) / CLOCKS_PER_SEC;
	printf ("\n\nTime taken = %6.1f secs.\t %d push operations\n\n\n", time, p);

}

void print_board()
{
    int i,j;

    printf("\n\n\n");

    for(i=N-1; i>=0; i--) {
        for(j=0; j<N; j++)
            printf("\t%d", board[j][i]);
        printf("\n\n");
    }
}


int     move_valid () {
            return ((newx >= 0) && (newx < N) &&
	        (newy >= 0) && (newy < N) &&
	        (board[newx][newy] == 0));
}

void try_move (int mt) {
    switch (mt) {
	case 1: 
	    newx = x + 1;
	    newy = y + 2;
	    break;
	case 2: 
	    newx = x + 2;
	    newy = y + 1;
	    break;
	case 3: 
	    newx = x + 2;
	    newy = y - 1;
	    break;
	case 4: 
	    newx = x + 1;
	    newy = y - 2;
	    break;
	case 5: 
	    newx = x - 1;
	    newy = y - 2;
	    break;
	case 6: 
	    newx = x - 2;
	    newy = y - 1;
	    break;
	case 7: 
	    newx = x - 2;
	    newy = y + 1;
	    break;
	case 8: 
	    newx = x - 1;
	    newy = y + 2;
	    break;
	default: 
	    printf ("Illegal move type %d in try_move", move_type);
	    exit (1);
    }
}


void retract_move () {
int mtype;
    if (!stack_empty())
	move_type = pop();
    else
	printf (" exiting\n\n"), exit (-1);
    board[x][y] = 0;

mtype =(move_type+4)%8;
if (mtype==0)mtype=8;
    try_move (mtype);
    x = newx;
    y = newy;
    move_number--;
}



Tks for help

Is This A Good Question/Topic? 0
  • +

Replies To: Stack and Knight Tour

#2 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1550
  • View blog
  • Posts: 4,930
  • Joined: 20-March 10

Re: Stack and Knight Tour

Posted 05 November 2018 - 03:14 AM

Well, first of all, understand the problem,

https://en.wikipedia...Knight%27s_tour

secondly, I don't think that's a viable solution to a knights tour,

You should be using Warnsdorffs Algorithm

https://www.geeksfor...s-tour-problem/

which will solve in a generic way for all N x N boards and not just a specific case like 6x6

But in any case, the retract_move is a backtracking function.

It pops the last legal move off the stack, that was used and tries to find another legal move I'm not convinced of the logic of it however it just looks wrong.
Was This Post Helpful? 2
  • +
  • -

#3 Major Tom   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 05-November 18

Re: Stack and Knight Tour

Posted 05 November 2018 - 03:51 AM

View Postsnoopy11, on 05 November 2018 - 03:14 AM, said:

Well, first of all, understand the problem,

https://en.wikipedia...Knight%27s_tour

secondly, I don't think that's a viable solution to a knights tour,

You should be using Warnsdorffs Algorithm

https://www.geeksfor...s-tour-problem/

which will solve in a generic way for all N x N boards and not just a specific case like 6x6

But in any case, the retract_move is a backtracking function.

It pops the last legal move off the stack, that was used and tries to find another legal move I'm not convinced of the logic of it however it just looks wrong.


How can you fix it? Please help....
Was This Post Helpful? 0
  • +
  • -

#4 Kintana   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 30-October 18

Re: Stack and Knight Tour

Posted 05 November 2018 - 06:53 AM

But you can explain for me about the retract_move function logic. And i have tested this code with all of N x N board and the result is right. So if the code have error about logic, can u give me something to fix that logic. Thanks a lot
Was This Post Helpful? 0
  • +
  • -

#5 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 14498
  • View blog
  • Posts: 58,117
  • Joined: 12-June 08

Re: Stack and Knight Tour

Posted 05 November 2018 - 07:47 AM

Who is this Major Tom feller wandering in and asking for a solution? Not the OP I assume?
Was This Post Helpful? 0
  • +
  • -

#6 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1550
  • View blog
  • Posts: 4,930
  • Joined: 20-March 10

Re: Stack and Knight Tour

Posted 06 November 2018 - 01:08 AM

Well Kintana,

There are a lot of things wrong really it claims to be c++ but is written in a very bad C style.

Why very bad ? Well it uses void main() instead of int main() it uses globals like nobody's business, and declares functions inside of main() etc, etc.

The program also does not work for all of N, N=8 gives an answer with N-1 rows and N columns instead of N rows and N columns.

Now to answer your question what does mtype =(move_type+4)%8; actually mean well mtype and move_type are types of moves that are outlined in the case statements of try_move they range from one to eight, the statement is saying add Four to move_type then take the modulus of Eight which is a way of getting the remainder of a division of Eight ie if move_type =6 then 6+4 = 10, 10/8 gives a remainder of two so the next move that would be tried would be case 2 in try_move().

why modulo Eight ? because there are Eight different types of possible move.

Now a more C++ approach using exactly the same code yet cleaner, and more logical than declaring function definitions inside of main()....

#include <iostream>
using namespace std;

#include <ctime>

#define N 8
#define STMAX N*N

class Stack
{
    int top=0;

    int a[STMAX];    //Maximum size of Stack
public:
    Stack()
    {

    }
    bool push(int x);
    int pop();
    bool isEmpty();
    bool isFull();
};

bool Stack::push(int x)
{

    a[++top] = x;

    return true;

}

int Stack::pop()
{


    return a[top--];

}

bool Stack::isEmpty()
{
    return (top <= 0);
}

bool Stack::isFull()
{
    return (top == STMAX);
}


class Board
{

public:
    int board[N][N]= {{0}};
    int move_type = 0;
    int  x=0,
         y=0,
         newx=0,
         newy=0,
         move_number;


    Board()
    {
        board[0][0]=1;
        move_number = 2;
        move_type=0;
        newx = x = 0;
        newy = y = 0;
    }

};





void retract_move (int& move_type, Stack& _stack, Board& board);
bool move_valid (Board& board);
void try_move (int mt, Board& board);
void print_board(Board& board);

int main ()
{

    int p=0;
    unsigned long t;
    double time;

    Stack _stack;

    Board board;

//  insert prior to the code you want to time
    t = clock();

    do
    {

        do
        {
            while (board.move_type == 8)
            {
                retract_move(board.move_type,_stack, board);
            }
            board.move_type++;
            try_move (board.move_type, board);

        }
        while (!move_valid (board));

        p++;
        _stack.push (board.move_type);
        board.x = board.newx;
        board.y = board.newy;
        board.move_type =0;

        board.board[board.x][board.y] = board.move_number++;
        if(board.move_number> N*N)
            print_board(board);

    }
    while (board.move_number <= N*N);

//  insert after to the code you want to time
    time = ((double)(clock() - t)) / CLOCKS_PER_SEC;
    cout <<endl <<endl << "Time taken = " << time <<" secs.\t "<< p << " push operations.";

    return 0;

}

void print_board(Board& board)
{


    cout << endl << endl << endl;

    for(int i=N-1; i>=0; i--)
    {
        for(int j=0; j<N; j++){
           cout << "\t" << board.board[j][i];
        }
        cout << endl << endl;
    }
}


bool     move_valid (Board& board)
{
    return ((board.newx >= 0) && (board.newx < N) &&
            (board.newy >= 0) && (board.newy < N) &&
            (board.board[board.newx][board.newy] == 0));
}

void try_move (int mt, Board& board)
{
    switch (mt)
    {
    case 1:
        board.newx = board.x + 1;
        board.newy = board.y + 2;
        break;
    case 2:
        board.newx = board.x + 2;
        board.newy = board.y + 1;
        break;
    case 3:
        board.newx = board.x + 2;
        board.newy = board.y - 1;
        break;
    case 4:
        board.newx = board.x + 1;
        board.newy = board.y - 2;
        break;
    case 5:
        board.newx = board.x - 1;
        board.newy = board.y - 2;
        break;
    case 6:
        board.newx = board.x - 2;
        board.newy = board.y - 1;
        break;
    case 7:
        board.newx = board.x - 2;
        board.newy = board.y + 1;
        break;
    case 8:
        board.newx = board.x - 1;
        board.newy = board.y + 2;
        break;
    default:
        cout << "Illegal move type " << mt << " in try_move." << endl;
        exit (1);
    }
}


void retract_move (int& move_type, Stack& _stack, Board& board)
{
    int mtype;
    if (!_stack.isEmpty())
        move_type = _stack.pop();
    else
        cout << " exiting" <<  endl, exit (-1);
    board.board[board.x][board.y] = 0;

    mtype =(move_type+4)%8;
    if (mtype==0)
        mtype=8;
    try_move (mtype, board);
    board.x = board.newx;
    board.y = board.newy;
    board.move_number--;
}



This post has been edited by snoopy11: 06 November 2018 - 02:58 AM

Was This Post Helpful? 2
  • +
  • -

#7 Salem_c   User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 2238
  • View blog
  • Posts: 4,325
  • Joined: 30-May 10

Re: Stack and Knight Tour

Posted 06 November 2018 - 03:28 AM

Just for reference, the OP's "code" is from this 8-year old thread they tried to hijack.
https://www.dreaminc...d-backtracking/
Was This Post Helpful? 1
  • +
  • -

#8 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1550
  • View blog
  • Posts: 4,930
  • Joined: 20-March 10

Re: Stack and Knight Tour

Posted 06 November 2018 - 03:41 AM

Ahh, I see Salem_c,

I thought the name Kintana was familiar but couldn't place it.

Bad Kintana bad!!
Was This Post Helpful? 1
  • +
  • -

#9 Kintana   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 30-October 18

Re: Stack and Knight Tour

Posted 06 November 2018 - 04:07 AM

Oh I'm so sorry. I just begin learn C++ so I want to find a lot of thing to learn. This is the first I join one group to learn online so tell me if I do something wrong. And thanks for your help.
Was This Post Helpful? 0
  • +
  • -

#10 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1550
  • View blog
  • Posts: 4,930
  • Joined: 20-March 10

Re: Stack and Knight Tour

Posted 06 November 2018 - 05:31 AM

No Kintana,

The only thing you did wrong was not to specifically give a source for your code base,

you did say it was a code you had found, just didn't say it was from a dreamincode post from 2010 and that the code belonged to Kain6622, its just nice to have references if possible, that's all.

No one has hit the -1 red button for you yet so hang on in there. ;)
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1