Knight's Tour recursive problem

[foahchon]

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 the problem(s) is/are. I have an idea as to what the problem is, but let me first post my code:

#include <iostream>
#include <iomanip>
 
using namespace std;
 
void InitializeBoard(int **board, int xSize, int ySize);
void DisplayBoard(int **board, int xSize, int ySize);
bool KnightsTour(int **board, int xCoor, int yCoor, int xSize, int ySize, int moveNum);
bool MoveIsValid(int **board, int xCoor, int yCoor, int xSize, int ySize);
 
int main()
{
    int xSize, ySize, xCoor, yCoor;
    int **board;
 
    do
    {
        cout << "Enter length and height of board, seperated by a" << endl
             << "space (each greater than zero): ";
        cin >> xSize >> ySize;
    } while ((xSize < 1) || (ySize < 1));
 
    do
    {
        cout << "Enter starting X coordinate in the range of 1-"
             << xSize << ": ";
        cin >> xCoor;
    } while ((xCoor > xSize) || (xCoor < 1));
 
    do
    {
        cout << "Enter starting Y coordinate in the range of 1-"
             << ySize << ": ";
        cin >> yCoor;
    } while ((yCoor > ySize) || (yCoor < 1));
 
    cout << "X: " << xSize << "; Y: " << ySize << endl;
    cout << "X Coor: " << xCoor << "; Y Coor: " << yCoor << endl;
 
    // Convert to zero-based coordinates (as opposed to one-based).
    xCoor--;
    yCoor--;
 
    cout << "---------------------------------------------------" << endl << endl;
 
    board = new int *[xSize];
    int **temp = board;
 
    for (int a = 0; a < xSize; a++)
    {
        *temp = new int[ySize];
        (temp)++;
    }
 
    InitializeBoard(board, xSize, ySize);
    DisplayBoard(board, xSize, ySize);
 
    cout << endl << "---------------------------------------------------" << endl;
    cout << "Executing Knight's Tour..." << endl;
 
    if (KnightsTour(board, xCoor, yCoor, xSize, ySize, 1))
    {
        cout << "Solution found: " << endl << endl;
        DisplayBoard(board, xSize, ySize);
    }
    else
    {
        cout << "No solution found." << endl << endl;
        DisplayBoard(board,xSize,ySize);
    }
 
    for(int i = 0; i < xSize; i++)
    {
        delete [] (*temp);
        (temp)++;
    }
 
    delete board;
 
    cout << "Press any key to continue...";
    cin.ignore(1000,'\n');
    cin.get();
 
    return 0;
}
 
void InitializeBoard(int **board, int xSize, int ySize)
{
    int x, y;
 
    for (x = 0; x < xSize; x++)
    {
        for (y = 0; y < ySize; y++)
        {
            board[x][y] = 0;
        }
    }
}
 
void DisplayBoard(int **board, int xSize, int ySize)
{
    int x, y;
 
    for (x = 0; x < xSize; x++)
    {
        for (y = 0; y < ySize; y++)
        {
            cout << setw(3) << board[x][y];
        }
        cout << endl;
    }
}
 
bool MoveIsValid(int **board, int xCoor, int yCoor, int xSize, int ySize)
{
    if ((xCoor < 0) || (xCoor >= xSize))
    {
        return false;
    }
 
    if ((yCoor < 0) || (yCoor >= ySize))
    {
        return false;
    }
 
    if (board[xCoor][yCoor] != 0)
    {
        return false;
    }
 
    return true;
}
 
bool KnightsTour(int **board, int xCoor, int yCoor, int xSize, int ySize, int moveNum)
{
    if (!MoveIsValid(board, xCoor, yCoor, xSize, ySize))
    {
        return false;
    }
 
    board[xCoor][yCoor] = moveNum;
 
    if ((xSize * ySize) == moveNum)
    {
        return true;
    }
 
    cout << "KT: " << yCoor << ", " << xCoor << ", " << moveNum << endl;
 
    if (!KnightsTour(board, (xCoor - 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
        if (!KnightsTour(board, (xCoor - 2), (yCoor - 1), xSize, ySize, (moveNum + 1)))
            if (!KnightsTour(board, (xCoor - 2), (yCoor + 1), xSize, ySize, (moveNum + 1)))
                if (!KnightsTour(board, (xCoor - 1), (yCoor + 2), xSize, ySize, (moveNum + 1)))
                    if (!KnightsTour(board, (xCoor + 1), (yCoor + 2), xSize, ySize, (moveNum + 1)))
                        if (!KnightsTour(board, (xCoor + 2), (yCoor + 1), xSize, ySize, (moveNum + 1)))
                            if (!KnightsTour(board, (xCoor + 2), (yCoor - 1), xSize, ySize, (moveNum + 1)))
                                if (!KnightsTour(board, (xCoor + 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
                                    return false;
 
    moveNum = 0;
    return true;
}
 

Here is the program's output:

Enter length and height of board, seperated by a
space (each greater than zero): 5 5
Enter starting X coordinate in the range of 1-5: 1
Enter starting Y coordinate in the range of 1-5: 1
X: 5; Y: 5
X Coor: 1; Y Coor: 1
---------------------------------------------------
 
  0  0  0  0  0
  0  0  0  0  0
  0  0  0  0  0
  0  0  0  0  0
  0  0  0  0  0
 
---------------------------------------------------
Executing Knight's Tour...
KT: 0, 0, 1
KT: 2, 1, 2
KT: 4, 0, 3
KT: 3, 2, 4
KT: 1, 1, 5
KT: 3, 0, 6
KT: 4, 2, 7
KT: 3, 4, 8
KT: 1, 3, 9
KT: 0, 1, 10
KT: 2, 0, 11
KT: 4, 1, 12
KT: 3, 3, 13
KT: 1, 2, 14
KT: 3, 1, 15
KT: 1, 0, 16
KT: 2, 2, 17
KT: 4, 3, 18
KT: 2, 4, 19
KT: 0, 3, 20
KT: 1, 4, 18
KT: 0, 2, 19
KT: 2, 3, 20
KT: 4, 4, 21
KT: 0, 4, 21
No solution found.
 
  1 16 11  6  3
 10  5  2 15 12
 19 14 17  4  7
 20  9 20 13 18
 21 18 19  8 21
Press any key to continue...
 

It appears moveNum is being reset somewhere (it goes from 1 to 20, then back to 18 again, and 21 is also repeated), but I can't figure out where. Any help on this would be greatly appreciated.

[AdrianH]

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 the problem(s) is/are. I have an idea as to what the problem is, but let me first post my code:

...
It appears moveNum is being reset somewhere (it goes from 1 to 20, then back to 18 again, and 21 is also repeated), but I can't figure out where. Any help on this would be greatly appreciated.

Interesting. I've not heard of this problem till you brought it up. Your code seems to be fairly good stylistically, but I would suggest comments on sections that are not straight forward such as:

    if (!KnightsTour(board, (xCoor - 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
        if (!KnightsTour(board, (xCoor - 2), (yCoor - 1), xSize, ySize, (moveNum + 1)))
            if (!KnightsTour(board, (xCoor - 2), (yCoor + 1), xSize, ySize, (moveNum + 1)))
                if (!KnightsTour(board, (xCoor - 1), (yCoor + 2), xSize, ySize, (moveNum + 1)))
                    if (!KnightsTour(board, (xCoor + 1), (yCoor + 2), xSize, ySize, (moveNum + 1)))
                        if (!KnightsTour(board, (xCoor + 2), (yCoor + 1), xSize, ySize, (moveNum + 1)))
                            if (!KnightsTour(board, (xCoor + 2), (yCoor - 1), xSize, ySize, (moveNum + 1)))
                                if (!KnightsTour(board, (xCoor + 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
 

Anyway, this is an AI search problem which requires backtracking as you would not be able to determine ahead of time what the result is. I don't have time right now, but I'll look at your code later. Please add comments to your code to make my (and others) reading easier.

Thanks,


Adrian

[foahchon]

Thanks for your reply. I've added some commenting. Hopefully this helps:

 
#include <iostream>
#include <iomanip>
 
using namespace std;
 
// Function prototypes.
void InitializeBoard(int **board, int xSize, int ySize);
void DisplayBoard(int **board, int xSize, int ySize);
bool KnightsTour(int **board, int xCoor, int yCoor, int xSize, int ySize, int moveNum);
bool MoveIsValid(int **board, int xCoor, int yCoor, int xSize, int ySize);
 
int main()
{
    int xSize, ySize, xCoor, yCoor;
    int **board;
 
    // Loop until user enters usable input for board's width, height,
    // and starting coordinates.
    do
    {
        cout << "Enter length and height of board, seperated by a" << endl
             << "space (each greater than zero): ";
        cin >> xSize >> ySize;
    } while ((xSize < 1) || (ySize < 1));
 
    do
    {
        cout << "Enter starting X coordinate in the range of 1-"
             << xSize << ": ";
        cin >> xCoor;
    } while ((xCoor > xSize) || (xCoor < 1));
 
    do
    {
        cout << "Enter starting Y coordinate in the range of 1-"
             << ySize << ": ";
        cin >> yCoor;
    } while ((yCoor > ySize) || (yCoor < 1));
 
    // Display debug information.
    cout << "X: " << xSize << "; Y: " << ySize << endl;
    cout << "X Coor: " << xCoor << "; Y Coor: " << yCoor << endl;
 
    // Convert to zero-based coordinates (as opposed to one-based).
    xCoor--;
    yCoor--;
 
    cout << "---------------------------------------------------" << endl << endl;
 
    // Make two-dimensional array out of pointers (assignment requirement).
    board = new int *[xSize];
    int **temp = board;
 
    for (int a = 0; a < xSize; a++)
    {
        *temp = new int[ySize];
        (temp)++;
    }
 
    // More debug information to make sure board is created and populated
    // with zeroes correctly.
    InitializeBoard(board, xSize, ySize);
    DisplayBoard(board, xSize, ySize);
 
    // Run Knight's Tour algorithm...
    cout << endl << "---------------------------------------------------" << endl;
    cout << "Executing Knight's Tour..." << endl;
 
    if (KnightsTour(board, xCoor, yCoor, xSize, ySize, 1))
    {
        cout << "Solution found: " << endl << endl;
        DisplayBoard(board, xSize, ySize);
    }
    else
    {
        cout << "No solution found." << endl << endl;
        DisplayBoard(board,xSize,ySize);
    }
 
    // Free up memory allocated for board.
    for(int i = 0; i < xSize; i++)
    {
        delete [] (*board);
        (board)++;
    }
 
    cout << "Press any key to continue...";
    cin.ignore(1000,'\n');
    cin.get();
 
    return 0;
}
 
// Function to initialize board (populate two-dimensional array
// with zeroes).
void InitializeBoard(int **board, int xSize, int ySize)
{
    int x, y;
 
    for (x = 0; x < xSize; x++)
    {
        for (y = 0; y < ySize; y++)
        {
            board[x][y] = 0;
        }
    }
}
 
// Display the board.
void DisplayBoard(int **board, int xSize, int ySize)
{
    int x, y;
 
    for (x = 0; x < xSize; x++)
    {
        for (y = 0; y < ySize; y++)
        {
            cout << setw(3) << board[x][y];
        }
        cout << endl;
    }
}
 
 
// Check to see if the move is valid (i.e. check to see if the coordinates
// aren't out of the board's bounds, and that the space isn't already occupied
// by a move number).
bool MoveIsValid(int **board, int xCoor, int yCoor, int xSize, int ySize)
{
    if ((xCoor < 0) || (xCoor >= xSize))
    {
        return false;
    }
 
    if ((yCoor < 0) || (yCoor >= ySize))
    {
        return false;
    }
 
    if (board[xCoor][yCoor] != 0)
    {
        return false;
    }
 
    return true;
}
 
 
// Knight's Tour algorithm.
bool KnightsTour(int **board, int xCoor, int yCoor, int xSize, int ySize, int moveNum)
{
    if (!MoveIsValid(board, xCoor, yCoor, xSize, ySize))
    {
        return false;
    }
 
    board[xCoor][yCoor] = moveNum;
 
    if ((xSize * ySize) == moveNum)
    {
        return true;
    }
 
    cout << "KT: " << yCoor << ", " << xCoor << ", " << moveNum << endl;
 
    // Each call to KnightsTour() looks for another potential square to move
    // onto.
    if (!KnightsTour(board, (xCoor - 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
        if (!KnightsTour(board, (xCoor - 2), (yCoor - 1), xSize, ySize, (moveNum + 1)))
            if (!KnightsTour(board, (xCoor - 2), (yCoor + 1), xSize, ySize, (moveNum + 1)))
                if (!KnightsTour(board, (xCoor - 1), (yCoor + 2), xSize, ySize, (moveNum + 1)))
                    if (!KnightsTour(board, (xCoor + 1), (yCoor + 2), xSize, ySize, (moveNum + 1)))
                        if (!KnightsTour(board, (xCoor + 2), (yCoor + 1), xSize, ySize, (moveNum + 1)))
                            if (!KnightsTour(board, (xCoor + 2), (yCoor - 1), xSize, ySize, (moveNum + 1)))
                                if (!KnightsTour(board, (xCoor + 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
                                    // At this point, there are no good moves left.
                                    return false;
}
 

As a little bit of background, the Knight's Tour is a sequence of moves by a knight (that is, the chess piece) that will visit every square exactly once. The program is supposed to output a matrix of non-repeating numbers, from 1 to the number of squares on the board, because the "knight" leaves a non-zero number on each square it has visited.

[Ganon11]

I'm pretty sure the reason moveNum is reseting is because of the recursion involved. For instance, if I've found a good path from 20-23. but move 24 is impossible, I should be able to backtrack and try a new path from 20 - but your function has already set 21, 22, and 23 in the board, so those spaces will count as occupied. You might be able to change your condition (board[xCoor][yCoor] == 0) to board[xCoor][yCoor] < moveNum.

This is a very interesting problem...

[AdrianH]

I'm pretty sure the reason moveNum is reseting is because of the recursion involved. For instance, if I've found a good path from 20-23. but move 24 is impossible, I should be able to backtrack and try a new path from 20 - but your function has already set 21, 22, and 23 in the board, so those spaces will count as occupied. You might be able to change your condition (board[xCoor][yCoor] == 0) to board[xCoor][yCoor] < moveNum.

This is a very interesting problem...

Sorry, I've still not read this programme. However, if what Ganon11 is saying is correct, then it should be easy to fix this by zeroing the cell when backtracking.

A simple solution for this would be to have:

• a function moveFrom() that passes the board and the count (unless you make those global or make it implicit by creating an object which contains this information), and the current position. moveFrom() will then:
  • set the current position with the current count
  • increment the count
  • determine a valid position to go to in a systematic way
  • and call moveFrom() with the new found valid position.
  • if moveFrom() returns false, then it couldn't find a path, so try next valid position.
  • if a complete path was not found and no more valid positions are found, then set current cell to 0 (if count is global or implicit, don’t forget to decrement it) and return false, otherwise, return true.

A complete path is determined if the count is equal to the total number of squares on the board.

Again, I apologise for not looking at your code. It was easier to spit out the algorithm and I've got to go.


Adrian

[foahchon]

Thanks for your replies.

I'm pretty sure the reason moveNum is reseting is because of the recursion involved. For instance, if I've found a good path from 20-23. but move 24 is impossible, I should be able to backtrack and try a new path from 20 - but your function has already set 21, 22, and 23 in the board, so those spaces will count as occupied. You might be able to change your condition (board[xCoor][yCoor] == 0) to board[xCoor][yCoor] < moveNum.

This is a very interesting problem...

I don't see that condition anywhere. There is (board[xCoor][yCoor] != 0), and I tried modifying that to (< moveNum), but then the board was changed completely to zeroes.

Sorry, I've still not read this programme. However, if what Ganon11 is saying is correct, then it should be easy to fix this by zeroing the cell when backtracking.

• a function moveFrom() that passes the board and the count (unless you make those global or make it implicit by creating an object which contains this information), and the current position. moveFrom() will then:
  • set the current position with the current count
  • increment the count
  • determine a valid position to go to in a systematic way
  • and call moveFrom() with the new found valid position.
  • if moveFrom() returns false, then it couldn't find a path, so try next valid position.
  • if a complete path was not found and no more valid positions are found, then set current cell to 0 (if count is global or implicit, don’t forget to decrement it) and return false, otherwise, return true.

A complete path is determined if the count is equal to the total number of squares on the board.

Adrian

Thanks for your time. That's pretty much what the KnightsTour() function that I have now does, I think. One thing it doesn't do, though, is set the cell to zero. I tried adding code earlier that set board[xCoor][yCoor] = 0, but I didn't know where to put it. I tried putting it after the last recursive KnightsTour() call, but then the matrix produced had zeroes in it.

Here are some notes from my class as to how the program should be written:

• Check to make sure it's not out of bounds (handled by MoveIsValid())
• Check to make sure sure you haven't been there before (also handled by MoveIsValid())
• Check to see if this move is the last (handled by ((xSize * ySize) == moveNum) condition).
• Eight recursive calls to KnightsTour()
• At the end, all eight moves are bad
• Remove number from board; board[xCoor][yCoor] = 0 (don't know where to put this)
• Have a default return statement (handled by "return false;")

As far as I can tell, I have everything implemented, except for the "remove number from the board" part.

Thanks again.

[foahchon]

I solved it (I think). I changed the last line in KnightsTour() to "return false;" to this:

if (!KnightsTour(board, (xCoor + 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
{
    board[xCoor][yCoor] = 0;
    return false;
}
 

Thanks for all your help.

[nmadct]

Generally speaking, a recursive solution like this is much easier to write if you avoid passing around a data structure that is modified using side effects (i.e. changing the values of variables). The side effects make it much more complicated to backtrack to a previous state, since you've overwritten the previous state. If you made a new copy of the board matrix every time you plotted a successful move, then you'd never have to worry about "undoing" moves when the code follows a dead-end path and has to backtrack.

[willakawill]

I solved it (I think). I changed the last line in KnightsTour() to "return false;" to this:

if (!KnightsTour(board, (xCoor + 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
{
    board[xCoor][yCoor] = 0;
    return false;
}
 

Thanks for all your help.

You have not solved the problem. Try again.
The fact that the recursion steps you back to a space from where you have a viable move left does not necessarily have to be a problem. I imagine that this could be a very useful 'feature' of your algorithm if implimented correctly. Each time you get stuck the program will go back to a previous position and start again. One of the things you have to do, as you have already been advised, is to reset the squares to zero that you have backtracked over. Another would be to ensure that you don't keep repeating the same two scenarios ad infinitum.
Good luck

[AdrianH]

Generally speaking, a recursive solution like this is much easier to write if you avoid passing around a data structure that is modified using side effects (i.e. changing the values of variables). The side effects make it much more complicated to backtrack to a previous state, since you've overwritten the previous state. If you made a new copy of the board matrix every time you plotted a successful move, then you'd never have to worry about "undoing" moves when the code follows a dead-end path and has to backtrack.

nmadct,

You are correct that it can be easier and when using a functional language (one that doesn't have object and global variables) it is actually required, but computationally, it is more resource intensive. So, for efficency, undoing a state change that was done to get there is actually a better idea.

Adrian

[AdrianH]

You have not solved the problem. Try again.
The fact that the recursion steps you back to a space from where you have a viable move left does not necessarily have to be a problem. I imagine that this could be a very useful 'feature' of your algorithm if implimented correctly. Each time you get stuck the program will go back to a previous position and start again. One of the things you have to do, as you have already been advised, is to reset the squares to zero that you have backtracked over. Another would be to ensure that you don't keep repeating the same two scenarios ad infinitum.
Good luck

Hi willakawill,

What exactly do you mean by "keep repeating the same two scenarios ad infinitum"? What two are you referring to?

Are you suggesting a heuristic? or perhaps detecting a similar sub-board configuration and discard the ones known to not lead to the goal? If so, what you are describing is using pattern recognition for board subsets.

It may possible, no doubt about it, but it also may not be trivial. AI is a course I really enjoyed in University and the discussion of search and how to implement it is a huge part of the course. In fact I think that was the course, because to reach the goal is to search for it.

Heuristics could be a viable way of doing this, but sometimes heuristics could not only cut off large portions of the search tree, but if not a good heuristic, it could also cut off the goal. However, there may be more than one path to the goal, so pruning some of the search branches which may have one or more goal paths may still not mean you have a bad heuristic, as it still may lead you to the goal faster.

But the question is, what is a good heuristic? Or are you thinking about getting the computer to detect it for you? That is also not trivial. However, this is all interesting, and I would suggest that you try it if interested. I can tell you this much, given Government and Wars, we need all the intelligence we can get, artificial or otherwise. :)


Adrian

[AdrianH]

I solved it (I think). I changed the last line in KnightsTour() to "return false;" to this:

if (!KnightsTour(board, (xCoor + 1), (yCoor - 2), xSize, ySize, (moveNum + 1)))
{
    board[xCoor][yCoor] = 0;
    return false;
}
 

Thanks for all your help.

No problem. Glad to help.


Adrian

[nmadct]

nmadct,

You are correct that it can be easier and when using a functional language (one that doesn't have object and global variables) it is actually required, but computationally, it is more resource intensive. So, for efficency, undoing a state change that was done to get there is actually a better idea.

Adrian

"Computationally" both methods are equivalent, in the sense that in the abstract they requre the same amount of computation. In terms of implementation, the cost of copying memory will slow things down. On a multi-CPU system, the copying approach would make parallelization feasible and would thus offer a great potential speedup. Granted, in any architecture, the copying method requires more memory. Which approach is a "better idea" depends on where you expect your program to run. A destructively updating appraoch will probably perform better on your home desktop, so you'd probably prefer it if you're writing AI for a game, but if you're planning to do a long-running computation on a supercomputer then you'll consider how you can parallelize your program.

[willakawill]

Hi willakawill,

What exactly do ...Adrian

When we step back to a position with a viable move we have 2 options:
1. we go with the new move just detected and then reset higher move numbers to zero
2. we reset higher move numbers to zero and allow the choice of all available moves except the move number we are replacing

Either way we are onto a potential infinite loop. Even though I am not suggesting an heuristic approach, I am pointing to the potential pitfalls of the current approach. Not for me to solve this puzzle. There are many brave attempts already online.

[nmadct]

A tip for you on this problem. When you have a program that you think is correct, test if for a smaller board first. I've written a solution, and if I run it for boards 5, 6 or 7 squares across, it starts spitting out solutions right away. It takes WAY longer for an 8 square board, too long to be useful for testing. (Don't try a board smaller than 5 squares because there are no solutions.)

[AdrianH]

When we step back to a position with a viable move we have 2 options:
1. we go with the new move just detected and then reset higher move numbers to zero
2. we reset higher move numbers to zero and allow the choice of all available moves except the move number we are replacing

Either way we are onto a potential infinite loop. Even though I am not suggesting an heuristic approach, I am pointing to the potential pitfalls of the current approach. Not for me to solve this puzzle. There are many brave attempts already online.

I still don't see. In the algorithm implemented, the squares that were moved upon were marked as squares that could not be moved upon again. Upon failure of finding a solution, backtracking occurred clearing the squares where the move didn't work to a point where there was another possible move that was not tried.

Perhaps if you stated an example for your 2 points, it would be clearer. I would like to understand what you are referring to.


Adrian

[AdrianH]

"Computationally" both methods are equivalent, in the sense that in the abstract they requre the same amount of computation. In terms of implementation, the cost of copying memory will slow things down. On a multi-CPU system, the copying approach would make parallelization feasible and would thus offer a great potential speedup. Granted, in any architecture, the copying method requires more memory. Which approach is a "better idea" depends on where you expect your program to run. A destructively updating appraoch will probably perform better on your home desktop, so you'd probably prefer it if you're writing AI for a game, but if you're planning to do a long-running computation on a supercomputer then you'll consider how you can parallelize your program.

I buy that. The algorithm devised needs to be scaled to the system you are planning to use it on. The abstract is only part of the problem, as one has to also consider computational limitations based on the hardware they are running on. Since most people don't have a supercomputer with multi-processor core architecture, to break up a non-IO bounded computation would actually be detrimental to the system, as you start gaining significant overhead when moving from one thread to another (which in this case far exceeds copying of structures which use memory). Though on a duel-core processor, you probably be able to increase the throughput by just under 2 time (probably closer to 1.5-1.75 times).


Adrian

[willakawill]

I still don't see. In the algorithm implemented, the squares that were moved upon were marked as squares that could not be moved upon again. Upon failure of finding a solution, backtracking occurred clearing the squares where the move didn't work to a point where there was another possible move that was not tried.

Perhaps if you stated an example for your 2 points, it would be clearer. I would like to understand what you are referring to.


Adrian

The squares were not cleared after backtracking. This gave us the 2 possible scenarios