# Backtrack algorithm

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;
};

• You can reqire a template type to conform to a specific type. Add the line requires PODType<ELEMENT>() after the template <XXX> line. (Valid in C++17 but good as a comment now). – Martin York Mar 20 '15 at 15:47
• @Loki I guess… I was thinking of static_assert( is_pod< ELEMENT>::type ) or sth like that – qdii Mar 20 '15 at 15:48
• @qdii, you should definitely static_assert that the type is POD, in the lack of C++17 concepts. – glampert Mar 20 '15 at 18:02

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.

• oh that's a bug, m_finish should be used. The purpose of process_solution is to give the possibility for an user of a class to use the solution (maybe print it?) when found and stop the research (by setting m_finish to true). – qdii Mar 20 '15 at 14:56
• why should I remove the asserts once it's working ? they are here to prevent me from introducing bugs if I ever modify the class, and they cause 0 overheard – qdii Mar 20 '15 at 14:58

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?