/*
 * e_054_dame.cpp
 *
 *  Created on: May 30, 2015
 *      Author: Marius
 */

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

namespace e_054_dame_nms
{
    int N;
    int sol_count = 0;

    vector<int> pos_dame;
    vector<char> diagA_occ, diagB_occ, lines_occ;
    vector<int> first_solution;

    void print_environment(string msg)
    {
        cout << msg << ": ";
        for (int i = 1; i <= N; i++)
            cout << pos_dame[i] << " ";
        cout << endl;
    }

    //auxiliary functions
    inline int diagA_id(int x, int y)
    {
        return y - x + N;
    }

    inline int diagB_id(int x, int y)
    {
        return y + x + -1;
    }

    inline bool is_position_valid(int da, int db, int line)
    {
        return lines_occ[line] == 0 && diagA_occ[da] == 0 && diagB_occ[db] == 0;
    }

    inline void setOccupancyValue(char occ, int da, int db, int line)
    {
        diagA_occ[da] = occ;
        diagB_occ[db] = occ;
        lines_occ[line] = occ;
    }

    void backtrack(int k)
    {
        if (k == N + 1)
        {
            //found a solution
            sol_count++;
            if (sol_count == 1) first_solution = pos_dame;
            // trick: a solution can be obtained from another solution if we turn around the table
            // that's why we allow the first queen to move only half the rows
            // we duplicate the number of solutions, 
            // except the case when N is even and the first queen is in the middle row
            if (N % 2 == 0 || pos_dame[1] != (N + 1) / 2) sol_count++;
            return;
        }

        //otherwise
        int end_i = N;
        // trick: a solution can be obtained from another solution if we turn around the table
        // that's why we allow the first queen to move only half the rows
        // we duplicate the number of solutions, 
        // except the case when N is even and the first queen is in the middle row
        if (k == 1) end_i = (N + 1) / 2;
        for (int i = 1; i <= end_i; i++)
        {
            int x = k, y = i;
            int da = diagA_id(x, y);
            int db = diagB_id(x, y);
            bool is_pos_valid = is_position_valid(da, db, y);
            if (!is_pos_valid) continue;

            //if the position is valid, occupy it
            pos_dame[x] = y;
            setOccupancyValue(1, da, db, y);
            //print_environment("Position assigned");
            //backtrack to the next position
            backtrack(k + 1);
            //done, revert the state of the environment
            pos_dame[x] = 0;
            setOccupancyValue(0, da, db, y);
            //print_environment("Position removed");
        }
    }
}

int main()
{
    using namespace e_054_dame_nms;

    string in_file = "damesah.in", out_file = "damesah.out";
    ifstream ifs(in_file.c_str());
    ifs >> N;
    ifs.close();

    pos_dame.resize(N + 1);
    diagA_occ.resize(2 * N);
    diagB_occ.resize(2 * N);
    lines_occ.resize(N + 1);
    std::fill(diagA_occ.begin(), diagA_occ.end(), 0);
    std::fill(diagB_occ.begin(), diagB_occ.end(), 0);
    std::fill(lines_occ.begin(), lines_occ.end(), 0);

    backtrack(1);

    ofstream ofs(out_file.c_str());
    for (int i = 1; i <= N; i++)
        ofs << first_solution[i] << " ";
    ofs << endl << sol_count;
    ofs.close();

    return 0;
}