This is the first backtracking algorithm I've implemented. It finds all unique (up to rotation, transposition, mirroring, etc) solutions to the following problem:

Place 8 queens on a standard chess board such that no queen is threatening any other queen. It's gotten a lot more messy since I profiled and optimized it, but the basic approach is a breadth-first search over all possible boards. At every placement, a board state is tested to see if is a valid partial solution; if not, it is eliminated from the search tree.

#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>

// solve 8 queens problem w/ backtracking
typedef struct 
{
    unsigned char rows[8];
} partial_p;

typedef union
{
    partial_p p;
    unsigned long long cmp;
} partial;

static inline bool
getbit( partial const & p, int bit )
{
    return ((p.cmp >> bit)&1)==1;
}

static inline bool
getbit( partial const & p, int x, int y )
{
    return getbit(p,x+(y<<3));
}

void
print_solution( partial const & p )
{
    std::cout << "\n";
    for(int y=0; y<8; ++y)
    {
        for(int x=0; x<8; ++x)
        {
            std::cout << (getbit(p,x,y)?"1":"-");
        }
        std::cout << "\n";
    }
}

inline bool 
operator< ( partial const & a, partial const & b )
{
    return a.cmp < b.cmp;
}

std::set<partial> solutions;

static inline void
setbit( partial &p, int bit )
{   
    unsigned long long mask = 1;
    mask <<= bit;
    p.cmp |= mask;
}

static inline partial
flipv( partial const & p )
{
    partial q;
    for(int i=0; i<8; ++i)
    {
        q.p.rows[i] = p.p.rows[7-i];
    }
    return q;
}

static inline partial
fliph( partial const & p )
{
    partial q;
    q.cmp = 0;
    for(int i=0; i<8; ++i)
    {
        // http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
        q.p.rows[i] = (p.p.rows[i] * 0x0202020202ULL & 0x010884422010ULL) % 1023;
    }
    return q;
}

static inline partial
transpose( partial const & p )
{
    partial q;
    q.cmp = 0;
    for(int y=0; y<8; ++y)
    {
        for(int x=0; x<8; ++x)
        {
            if(getbit(p,x+(y<<3)) )
                setbit(q,(x<<3)+y);
        }
    }
    return q;
}

static inline bool
valid_cols_n_rows( partial const & p )
{
    bool valid(true);
    unsigned char taken(0);
    unsigned char c;
    for(int i=0; valid && i<8; ++i)
    {
        c = p.p.rows[i];
        valid = valid && ((taken & c)==0);
        valid = valid && ((c & (c-1))==0);  // 0 or 2^k
        taken |= p.p.rows[i];
    }
    return valid;
}

static inline bool
validdiags( partial const & p )
{
    static int sums[30];

    for(int i=0; i<30; ++i)
    {
        sums[i]=0;
    }
    
    for(int y=0; y<8; ++y)
    {
        for(int x=0; x<8; ++x)
        {
            // this pixel falls in two different diagonals
            if( getbit(p,x,y) )
            {
                // negative diagonals
                sums[x+y]++;     // x+y goes 0..14
                sums[x-y+22]++;  
                if(sums[x+y]>1||sums[x-y+22]>1)
                    return false;
            }
        }
    }
   
    return true;
}

bool
valid( partial const & p )
{
    //return validrows(p) && validcols(p) && validdiags(p);   
    return valid_cols_n_rows(p) && validdiags(p);
}

void 
compute_partials( std::vector<partial> & ps, partial const & p )
{
    for(int i=0; i<64; ++i)
    {
        if( !getbit(p,i) )
        {
            partial pp = p;
            setbit(pp,i);
            if( valid(pp) )
            {
                ps.push_back(pp);
            }
        }
    }
}

bool unique( partial const & p )
{
    partial q;
    if( solutions.count(p)>0 )
        return false;
    q = flipv(p);
    if( solutions.count(q)>0 )
        return false;
    q = fliph(q);
    if( solutions.count(q)>0 )
        return false;
    q = flipv(q);
    if( solutions.count(q)>0 )
        return false;
    q = transpose(q);
    if( solutions.count(q)>0 )
        return false;
    q = flipv(q);
    if( solutions.count(q)>0 )
        return false;
    q = fliph(q);
    if( solutions.count(q)>0 )
        return false;
    q = flipv(q);
    if( solutions.count(q)>0 )
        return false;
    return true;
}

int
main()
{
    partial p;
    p.cmp = 0;
    solutions.insert(p);
    
    std::cout << "--------------------------------------------------------------\n";
    std::cout << "This program solves the 8-queens problem on an 8x8 grid.      \n";
    std::cout << "The point of this problem is to find positions for 8 queens.  \n";
    std::cout << "on a chessboard such that none of them can attack one another.\n";
    std::cout << "--------------------------------------------------------------\n\n";
    
    std::cout << "Press enter to begin...\n";
    std::cin.ignore();
    
    for(int i=0; i<8; ++i)
    {
        std::cout << "- Partial solutions so far: " << solutions.size() << "\n";
        std::vector<partial> next;
        for(std::set<partial>::iterator it=solutions.begin(); 
            it!=solutions.end(); ++it )
        {
            compute_partials( next, *it );
        }
        solutions.clear();
        for(int j=0; j<next.size(); ++j)
        {
            if( unique( next[j] ) )
                solutions.insert( next[j] );
            
        }
    }
    
    std::cout << "\n" << solutions.size() << " fundamental solutions found: \n\n";
    std::cout.flush();
    std::set<partial>::iterator it;
    int solno=1;
    for(it=solutions.begin(); it!=solutions.end(); it++)
    {
        std::cout << "Solution #" << solno++ << "\n";
        print_solution(*it);
        if( solno <= solutions.size() )
        {
            std::cout << "\nPress enter to see the next solution.\n";
            std::cin.get();
        }
    }
    std::cout << "\nThanks for checking it out.\n\nPeace.";
}