Finding non-self-intersecting paths of certain moves that touch all points in a grid

Question

The problem I'm trying to solve is the following:

You have a 10x10 grid and starting from the upper-left point you have to touch all the points, without passing through the points that have already been touched, with a limited set of moves. Horizontally you can move by three points and diagonally you can move by two points.

Having tried it unsuccessfully multiple times by hand, I implemented a recursive brute-force algorithm in c++, encapsulating it in a class.

Vec2 is a helper class I made to keep the code cleaner and it is just an integer 2d vector class.

The main function is the bruteForce(), which searches for all possible moves from a position and recursing until there are no possible moves left, and while recursing it stores the moves it has done in a vector.

The problem is solved when there are no moves left and the size of the moves vector is 99.

The moves are stored in a clockwise order, starting from right to up-right and it's controlled via the following functions:

• The isPossibleMove() returns true if, for a given position a move is possible and otherwise false
• The getPossibleMoves() stores all the possible moves from a given position in a vector; it starts searching from the last move(this drastically decreases time to find the first solutions)
• The getArrayIndex() is used to get the array indices from 2d coordinates(the array is row-major)

Board is the vector containing the 10x10 boolean grid (1 if the point has been touched, 0 otherwise), unique to each recursion step

The best that I could do to make it faster, was to use OpenMP in the first step, creating in this case, 3 threads. On my setup, it takes about 20 ms to find the first solution and about 1200 ms to find the first 1000 solutions.

So, how can it be faster?

It looks like this:

#include <vector>
#include <array>
#include "Point.h"

typedef Vec2 Point;

template<int gridSize>
class Solver
{
private:
    std::array<Vec2, 8> moves;
    bool solved;

    void initMoves()
    {
        moves[0] = Vec2(3, 0);
        moves[1] = Vec2(2, 2);
        moves[2] = Vec2(0, 3);
        moves[3] = Vec2(-2, 2);
        moves[4] = Vec2(-3, 0);
        moves[5] = Vec2(-2, -2);
        moves[6] = Vec2(0, -3);
        moves[7] = Vec2(2, -2);
    }

    bool isPossibleMove(const Point& p, int move, const std::vector<bool> &board) const
    {
        Point p1 = p;
        p1 += moves[move];

        return ((p1.getX() >= 0 && p1.getX() < gridSize && p1.getY() >= 0 && p1.getY() < gridSize) && !board[getArrayIndex(p1)]);
    }

    bool getPossibleMoves(const Point& p, const std::vector<bool> &board, int lastMove, std::vector<short>& possibleMoves) const //BECOMES BOOL
    {
        for (int i = lastMove; i < moves.size(); i++)
        {
            if (isPossibleMove(p, i, board))
            {
                possibleMoves.push_back(i);
            }
        }

        for (int i = 0; i < lastMove; i++)
        {
            if (isPossibleMove(p, i, board))
            {
                possibleMoves.push_back(i);
            }
        }

        return !possibleMoves.empty();
    }

    int getArrayIndex(const Vec2& vec) const
    {
        return vec.getX() + vec.getY() * gridSize;
    }

    bool verifySolution(const std::vector<short>& seq, const Vec2& start) const
    {
        Vec2 p = start;

        std::vector<bool> board(gridSize*gridSize, 0);

        board[getArrayIndex(p)] = 1;
        for (const auto &move : seq)
        {
            p += moves[move];
            board[getArrayIndex(p)] = 1;
        }

        for (const auto &i : board)
        {
            if (i == 0)
            {
                return false;
            }
        }

        return true;
    }

    void bruteForce(Point p, std::vector<short> seq, std::vector<bool> board)
    {
        if (!solved)
        {
            std::vector<short> possibleMoves;
            possibleMoves.reserve(8);

            board[getArrayIndex(p)] = 1;
            p += moves[seq.back()];

            while (getPossibleMoves(p, board, seq.back(), possibleMoves))
            {
                for (auto i = possibleMoves.begin(); i < possibleMoves.end() - 1; ++i)
                {
                    seq.push_back(*i);
                    bruteForce(p, seq, board);
                    seq.pop_back();
                }

                seq.push_back(possibleMoves.back());
                possibleMoves.resize(0);

                board[getArrayIndex(p)] = 1;
                p += moves[seq.back()];

            } 


            if (seq.size() == gridSize * gridSize - 1 && !solved)
            {
                std::cout << "SOLVED!!!!!\n";
                solved = true;
            }
        }
    }

public:
    Solver() : solved(false)
    {
        initMoves();
    }

    void start(Point p = Point(0, 0))
    {
        std::vector<bool> board(gridSize*gridSize, 0);
        board[getArrayIndex(p)] = 1;

        std::vector<short> possibleMoves;
        getPossibleMoves(p, board, 0, possibleMoves);

        for (const auto& i : possibleMoves)
        {
            bruteForce(p, std::vector<short>(1, i), board);
        }
    }

    void startOpenMP(Point p = Point(0, 0))
    {
        std::vector<bool> board(gridSize*gridSize, 0);
        board[getArrayIndex(p)] = 1;

        std::vector<short> possibleMoves;
        getPossibleMoves(p, board, 0, possibleMoves);

#pragma omp parallel for
        for (int i = 0; i < possibleMoves.size(); i++)
        {
            bruteForce(p, std::vector<short>(1, possibleMoves[i]), board);
        }
    }
};

Answer 1

Get rid of the vectors

Normally, std::vector is your friend in C++. But it is a dynamically allocated structure. Constructing the vector and pushing back is therefore costly, and you are doing it a lot.

Since you only have at most four possible moves every step, just use a fixed size array to store them, and use either another variable to store how many moves are stored in that array, or use a guard value (like -1) to indicate that an entry in the array is not valid.

Secondly, there is no need to use a vector seq to store the path. Instead, make board be a 10x10 array of shorts that store the next section of the path. For example, the top left entry in the array will store the coordinates (1, 0) if the path goes to the right, or (0, 1) if it goes down. Again, have a guard value to indicate that a position is not seen yet.

Points vs indices

Currently, you are using Point to store positions. However, this is not optimal. First, it is probably a pair of ints, so it will take up 64 bits on most computers today, when you only need a number <= 100 to store the position on the board. Second, if the implementation of getX() and getY() is not defined in the header file Point.h, but rather in Point.c, then the compiler will not be able to inline it, and will generate function calls. These will take a lot of time compared to just accessing a member variable directly. Third, you have to convert between points coordinates and positions in the array. While quite trivial, it can be avoided.

Instead of using x/y coordinates, just use a regular int to store indices into the board. A short may or may not be faster. To go left or right, just add or subtract one from the index; to go down or up, just add or subtract 10. You will need to add checks to make sure you don't go off an edge of course, but you had to do that anyway.

Answer 2

Interface

It's pretty common to order your interface from least to most restricting. I.e. public, protected, private. This way users of your class don't have to scroll all the way down only to see what methods you expose.

vector<bool> is special

It can have an impact on performance so you might want to reconsider its usage. If you do use vector make sure to use reserve to avoid unnecessary allocations.

Early out

In many cases it's a good idea to opt for an early out if things go wrong.
So instead of:

if (condition) {
    // do things
}

prefer:

if (!condition) {
    return;
}

// other code here

This way you avoid arrow code that grows more and more to the right of your screen

Misc.

In some cases you still use foo & instead of the recommended foo&. Copy paste error?

Why do you use typedef and then continue to use Point in most cases? This seems inconsistent. You said Point is your own implementation so if you want a different name just rename the class/struct.

Interesting use of template. Is there a specfic reason why you don't just pass gridSize as a parameter?
On this note, if you intend to use this code to solve arbitrary sized grids you might blow up your stack.