马踏棋盘

马踏棋盘问题，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。

#include <tr1/tuple>
#include <cstdio>

template <int width, int height>
struct chess
{
    static const int x_[8];
    static const int y_[8];

    int nodelinks_[width * height];
    int cat(int x, int y) const { return nodelinks_[x + width * y]; }
    int& at(int x, int y) { return nodelinks_[x + width * y]; }

    chess();

    void go(int x, int y)
    {
        for (int i = 0; i < 8; ++i)
        {
            int a = x + x_[i], b = y + y_[i];
            if (a >= 0 && b >= 0 && a < width && b < height && cat(a,b) > 0)
                at(a,b) -= 1;
        }
        static int number = 0;
        at(x,y) = --number;
    }

    std::pair<int, int> next(int x, int y) const
    {
        int j = 0;
        for (int i = 0, v = 8; i < 8; ++i)
        {
            int a = x + x_[i], b = y + y_[i];
            if (a >= 0 && b >= 0 && a < width && b < height)
                if (cat(a,b) > 0 && cat(a,b) < v)
                    j = i, v = cat(a,b);
        }
        return std::make_pair(x + x_[j], y + y_[j]);
    }

    void print() const
    {
        for (int x = 0; x < width; ++x)
        {
            for (int y = 0; y < height; ++y)
                printf("%3d ", cat(x,y));
            puts("");
        }
    }
};

template <int width, int height>
chess<width, height>::chess()
{
    const int X = width - 1;
    const int Y = height - 1;
    for (int x = 2; x < width-2; ++x)
        for (int y = 2; y < height-2; ++y)
            at(x,y) = 8;
    for (int x = 2; x < width-2; ++x)
    {
        at(x,1) = at(x,Y-1) = 6;
        at(x,0) = at(x,Y) = 4;
    }
    for (int y = 2; y < height-2; ++y)
    {
        at(1,y) = at(X-1,y) = 6;
        at(0,y) = at(X,y) = 4;
    }
    at(0,0) = at(X,0) = at(0,Y) = at(X,Y)= 2;
    at(1,1) = at(X-1,1) = at(1,Y-1) = at(X-1,Y-1)= 4;
    at(0,1) = at(0,Y-1) = at(1,0) = at(X-1,0) = at(X,1) = at(X,Y-1) = at(X-1,Y) = at(1,Y) = 3;
}

template <int width, int height> const int chess<width, height>::x_[] = { -1, -1,  1, 1, -2, -2,  2, 2 };
template <int width, int height> const int chess<width, height>::y_[] = { -2,  2, -2, 2, -1,  1, -1, 1 };


////
namespace tr1 = std::tr1;

int main(int argc, char* argv[])
{
    chess<8, 8> tab;
    int x = 0, y = 0;
    tab.go(x, y);
    for (int i = 1; i < 64; ++i)
    {
        tr1::tie(x, y) = tab.next(x, y);
        tab.go(x, y);
    }
    tab.print();
}



#if 0
 -1 -16 -59 -34  -3 -18 -21 -36 
-58 -33  -2 -17 -60 -35  -4 -19 
-15 -54 -57 -62 -43 -20 -37 -22 
-32 -63 -46 -53 -56 -61 -42  -5 
-49 -14 -55   0 -47 -44 -23 -38 
-28 -31 -48 -45 -52 -41  -6  -9 
-13 -50 -29 -26 -11  -8 -39 -24 
-30 -27 -12 -51 -40 -25 -10  -7 


  0   1   2   3   4   5   6   7
0 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
1 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
2 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
3 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
4 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
5 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
6 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
7 +---+---+---+---+---+---+---+

      @---+---@
      |   |   |
  @---+---+---+---@
  |   |   |   |   |
  +---+---@---+---+
  |   |   |   |   |
  @---+---+---+---@
      |   |   |
      @---+---@
#endif

combination

#include <boost/range.hpp>
#include <vector>

template <typename t, typename op_t>
struct combination : private op_t, boost::noncopyable
{
    std::vector<t> res_;
    combination(int n, op_t op) : op_t(op), res_(n) {}
    template <typename iterator> void com(iterator begin, iterator end, int n);
};

template <typename t, typename op_t>
template <typename iterator>
void combination<t, op_t>::com(iterator begin, iterator end, int n)
{
    if (n == 1)
    {
        for ( ; begin != end; ++begin)
        {
            res_.back() = *begin;
            this->operator()(boost::begin(res_), boost::end(res_));
        }
        return;
    }

    while (begin + n < end)
    {
        res_[res_.size()-n] = *begin;
        this->com(++begin, end, n-1);
    }

    for ( ; begin != end; ++begin, --n)
        res_[res_.size()-n] = *begin;
    this->operator()(boost::begin(res_), boost::end(res_));
}

template <typename rng_t, typename op_t>
inline void combine(rng_t& r, int n, op_t op)
{
    typedef typename boost::range_value<rng_t>::type type;
    combination<type, op_t>(n, op).com(boost::begin(r), boost::end(r), n);
}


#include <algorithm>
#include <iostream>

struct Print
{
    template <typename iterator>
    void operator()(iterator begin, iterator end) const
    {
        typedef typename std::iterator_traits<iterator>::value_type type;
        std::vector<type> buf(begin, end);
        do
        {
            std::copy(buf.begin(), buf.end(), std::ostream_iterator<type>(std::cout));
            std::cout << " ";
        } while (std::next_permutation(buf.begin(), buf.end()));
        std::cout << std::endl;
    }
};

int
main(int argc, char* const argv[])
{
    char s[] = "12345";
    combine(s, 3, Print());
}


#if 0
123 132 213 231 312 321 
124 142 214 241 412 421 
125 152 215 251 512 521 
134 143 314 341 413 431 
135 153 315 351 513 531 
145 154 415 451 514 541 
234 243 324 342 423 432 
235 253 325 352 523 532 
245 254 425 452 524 542 
345 354 435 453 534 543 
#endif

8 queens

在8×8的国际象棋棋盘上放置8个皇后，要求任意两个皇后不能在同一行、同一列或同一条对角线上。

#include <cstdio>
#include <cstdlib>

void print(int cols[], int N);

inline bool is_safe(int cols[], int y)
{
        for (int i = 0; i < y; ++i)
                if (cols[i] == cols[y] || abs(cols[i] - cols[y]) == y - i)
                        return false;
        return true;
}

void queens(int cols[], int n, int N)
{
        if (n == N)
                return print(cols, N);
        for (int i = 0; i < N; ++i)
        {
                cols[n] = i;
                if (is_safe(cols, n))
                        queens(cols, n+1, N);
        }
}

int main()
{
        int cols[8] = { 0 };
        queens(cols, 0, sizeof(cols) / sizeof(int));
}

inline void prtn(const char* s, int n, const char* t = "")
{
        for (int i = 0; i < n; ++i)
                printf(s);
        printf(t);
}

void print(int cols[], int N)
{
        for (int y = 0; y < N; ++y)
                prtn("+---", N, "+\n"),
                prtn("|   ", cols[y], "| Q "), prtn("|   ", N-cols[y]-1, "|\n");
        prtn("+---", N, "+\n\n");
}

+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | Q |
+---+---+---+---+---+---+---+---+
|   |   |   | Q |   |   |   |   |
+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   | Q |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | Q |   |   |
+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | Q |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | Q |   |   |   |
+---+---+---+---+---+---+---+---+

约瑟夫问题

约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再重新报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的序号。

#include <cstdio>
#include <cstdlib>

inline int next(unsigned int x, int m, int vec[], int n)
{
    do
        while (vec[x % n])
            ++x;
    while (--m && ++x);
    return x % n;
}

int ysf(int n, int m)
{
    int x = 0, *vec = (int*)calloc(n, sizeof(int));
    for (int i = 1; i < n; ++i)
        vec[x = next(x, m, vec, n)] = 1;
    x = next(x, 1, vec, n);
    free(vec);

    return x + 1;
}

int main(int argc, char* const argv[])
{
    printf("%d\n", ysf(atoi(argv[1]), atoi(argv[2])));
}