n_queens_solution.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c) 2013 Piotr Wygocki
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_N_QUEENS_SOLUTION_HPP
#define PAAL_N_QUEENS_SOLUTION_HPP

#include "paal/utils/irange.hpp"

#include <boost/iterator/counting_iterator.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/range/numeric.hpp>

#include <vector>

namespace paal {
namespace local_search {

template <typename NQueensPositionsVector> struct n_queens_solution_adapter {
    typedef typename boost::counting_iterator<int> QueensIterator;

    n_queens_solution_adapter(NQueensPositionsVector &pos)
        : m_queen_position(pos),
          m_numeber_attacing_diagonal_negative(boost::distance(pos), 0),
          m_numeber_attacing_diagonal_nonnegative(boost::distance(pos), 0),
          m_numeber_attacing_counter_diagonal(2 * boost::distance(pos), 0) {
        for (auto q : irange(boost::distance(pos))) {
            increase(q);
        }
    }

    QueensIterator begin() const { return QueensIterator(0); }

    QueensIterator end() const {
        return QueensIterator(m_queen_position.size());
    }

    void swap_queens(int xLeft, int xRight) {
        int leftPosition = m_queen_position[xLeft];
        put_queen(xLeft, m_queen_position[xRight]);
        put_queen(xRight, leftPosition);
    }

    int get_num_attacing(int x, int y) const {
        return m_numeber_attacing_counter_diagonal[x + y] + get_diagonal(x, y);
    }

    int get_y(int x) const { return m_queen_position[x]; }

    int obj_fun() const {
        auto attacingNr = [](int sum, int n) { return sum + n * (n - 1) / 2; };
        int sum = boost::accumulate(m_numeber_attacing_counter_diagonal, 0,
                                    attacingNr);
        sum = boost::accumulate(m_numeber_attacing_diagonal_negative, sum,
                                attacingNr);
        return boost::accumulate(m_numeber_attacing_diagonal_nonnegative, sum,
                                 attacingNr);
    }

  private:

    void put_queen(int x, int y) {
        decrease(x);
        m_queen_position[x] = y;
        increase(x);
    }

    int &get_diagonal(int x) { return get_diagonal(x, m_queen_position[x]); }

    int &get_diagonal(int x, int y) {
        if (x >= y) {
            return m_numeber_attacing_diagonal_negative[x - y];
        } else {
            return m_numeber_attacing_diagonal_nonnegative[y - x];
        }
    }

    int get_diagonal(int x, int y) const {
        if (x >= y) {
            return m_numeber_attacing_diagonal_negative[x - y];
        } else {
            return m_numeber_attacing_diagonal_nonnegative[y - x];
        }
    }

    void decrease(int x) {
        --m_numeber_attacing_counter_diagonal[x + m_queen_position[x]];
        --get_diagonal(x);
    }

    void increase(int x) {
        ++m_numeber_attacing_counter_diagonal[x + m_queen_position[x]];
        ++get_diagonal(x);
    }

    NQueensPositionsVector &m_queen_position;
    std::vector<int> m_numeber_attacing_diagonal_negative;
    std::vector<int> m_numeber_attacing_diagonal_nonnegative;
    std::vector<int> m_numeber_attacing_counter_diagonal;
};

} 
} 

#endif // PAAL_N_QUEENS_SOLUTION_HPP