Backtrack algorithm

Question

I coded this algorithm in order to have a generic backtracking algorithm. I expect the user to pass a POD for ELEMENT, hopefully as small as possible. Any idea how I could improve this?

#ifndef BACKTRACK_H
#define BACKTRACK_H

#include <array>
#include <vector>
#include <assert.h>

template< class ELEMENT, unsigned MAX_CAPACITY >
class backtrack
{
public:
    backtrack()
        : m_grid()
        , m_depth( 0 )
        , m_finish( false )
    {
    }

    virtual ~backtrack() {}

    template< typename ForwardIterator >
    backtrack( ForwardIterator begin, ForwardIterator end )
        : m_grid()
        , m_depth( 0 )
        , m_finish( false )
    {
        std::copy( begin, end, m_grid.begin() );
    }

    void step()
    {
        if ( is_a_valid_solution( m_grid ) )
            m_finish = process_solution( m_grid );

        if ( m_depth == MAX_CAPACITY )
            return;

        const auto & candidates = generate_candidates( m_grid );
        for( const auto & candidate : candidates )
        {
            push( candidate );
            step();
            pull();
        }
    }

private:
    virtual
    bool is_a_valid_solution( const std::array< ELEMENT, MAX_CAPACITY > & solution )
    {
        ( void )solution;
        return false;
    }

    virtual
    bool process_solution( const std::array< ELEMENT, MAX_CAPACITY > & solution )
    {
        ( void )solution;
        return false;
    }

    virtual
    std::vector<ELEMENT> generate_candidates( const
            std::array< ELEMENT, MAX_CAPACITY > & partial_solution )
    {
        ( void )partial_solution;
        return std::vector<ELEMENT>();
    }

    void push( ELEMENT candidate )
    {
        assert( m_depth < MAX_CAPACITY );
        m_grid[ m_depth++ ] = candidate;
    }

    void pull()
    {
        assert( m_depth <= MAX_CAPACITY );
        assert( m_depth > 0 );
        m_grid[ --m_depth ] = ELEMENT();
    }

private:
    std::array< ELEMENT, MAX_CAPACITY > m_grid;
    unsigned m_depth;
    bool m_finish;
};

Answer 1

m_finish is never used (except for being set), better get rid of things not in use.

Purpose of process_solution is not clear for me. Why not just to save solutions and have accessor for them?

(void) solution. Is it a weird technique to eliminate warnings? Compiler warn you that you should make methods pure, because parent class relies on children overriding them.

generate_candidates. Better to use iterator pattern to make things more generic and hopefully eliminate unnecessary allocations.

I see no evidence that ELEMENT must be POD. It needs to have defaut constructor though, which is unfortunate. std::stack can help with it, as Yann pointed out.

What is the purpose of asserts? They assert class invariants, which should be ensured by the code of the class. Once you have it tested and working, you should consider to remove debugging code to make it more clear.

Consider renaming candidates to moves and grid to path to create nice conceptual model story. Now that names do not say much. Depth and capacity will become length, I think this will be more understandable.

How implementer will know the actual size of partial solution? Again, stack will help here, or pass m_depth along array, the latter is inferior solution, though.

Answer 2

Put in some braces around your if statements, even if it's just a 1 line result. Have a read of apple's goto fail bug if you want a reason why. Basically, remember that one day you may come back to this, delete something, add something then forget to factor in the flow. Make life wasy for yourself.

Unless I'm misreading something, you seem to be using an std::array as a stack. std::stack is a thing that you might want to consider using, unless you have particular reasons not to?