This code solves Dudeney's "The Miller's puzzle"

dudeney_miller.cpp

/*
    this code solves one of the Dudeney's Canterbury Puzzles,
    namely The Miller's Puzzle.

    My input was an italian blog, i.e.
    http://rudimatematici-lescienze.blogautore.espresso.repubblica.it/2015/06/07/lenigma-del-mugnaio/

    But you can find all the puzzles (thus even the miller's puzzle)
    here:

    http://www.gutenberg.org/files/27635/27635-h/27635-h.htm

    Assumption(s): 
      1) “as little trouble as possible” means that among the
         acceptable permutations, you have to pick the one with
         the minimum number of swaps (minimum distance); 
         it does not mean you have to choose the algorithm that 
         minimizes the number of swaps.
      2) it doesn't matter which sorting algorithm you use
         (provided it swaps elements…): every plausible algo
         through which we define a “distance” (number of swaps)
         preserves the “ordering”; thus,
         if d1(P0, P1) ≤ d1(P0, P2), then
         it will be true also that d2(P0, P1) ≤ d2(P0, P2), 
         for each permutations P1 and P2 (when 
         d1(P0, P1) = d2(P0, P2) holds, P1 and P2 are the same 
         permutation).
    
    The distance between initial permutation and each
    permutation satifying the conditions is computed counting
    the number of swaps in two different sorting algorithms:
    bubble sort and selection sort. The latter is supposed to
    be the one. Nonetheless, see assumption 2 (it should be
    proved; indeed, using 543691827 as P0, we find that the 
    assumption doesn't hold...)
 */
#include <iostream>
#include <iomanip>
#include <vector>
#include <climits>
#include <string>
#include <sstream>
#include <algorithm>



struct permstock
{
    int perm[9];
    std::string str() {
        std::stringstream ss;
        ss << perm[0] << "*" << perm[1] << perm[2] <<
            " = " << perm[3] << perm[4] << perm[5] <<
            " = " << perm[6] << perm[7] << "*" << perm[8];
        return ss.str();
    }
};

// the initial permutation (P0); we compute distances from this one
static permstock from { {7, 2, 8, 1, 9, 6, 3, 4, 5} };


// permutation's digits abcdefghi must satisfy:
bool satisfy(int* b)
{
    int a = b[0];
    int bc = b[1]*10 + b[2];
    int def = b[3]*100 + b[4]*10 + b[5];
    int gh = b[6]*10 + b[7];
    int i = b[8];
    return (a*bc == def) && (gh * i == def);
}


// compute distance
int calc_dist(int* to, bool bubble = true)
{
    int dist = 0;
    int po[9];
    int i, j;
    std::vector<int> l(to, to+9);

    for (i = 0; i < 9; ++i) {
        po[from.perm[i] - 1] = i;
    }

    if (bubble) {
        bool swap_done;
        do {
            swap_done = false;
            for (i = 0; i < (9-1); ++i) {
                if (po[l[i]-1] > po[l[i+1]-1]) {
                    int t = l[i];
                    l[i] = l[i+1];
                    l[i+1] = t;
                    swap_done = true;
                    ++dist;
                }
            }
        } while (swap_done);
    } else { // selection
        for (j = 0; j < (9-1); ++j) {
            int jmin = j;
            for (i = j+1; i < 9; ++i) {
                if (po[l[i]-1] < po[l[jmin]-1]) {
                    jmin = i;
                }
            }
            if (jmin != j) {
                int t = l[j];
                l[j] = l[jmin];
                l[jmin] = t;
                ++dist;
            }
        }
    }

    return dist;
}

// find the solution
void calc(bool mode, std::vector<permstock>& v)
{
    int min_len = INT_MAX;
    std::string min_str("");

    for (auto& x : v) {
        int d = calc_dist(x.perm, mode);
        
        if (d < min_len) {
            min_len = d;
            min_str = x.str();
        }
        
        if (min_len == 0)
            break;
    }

    std::cout << (mode ? "bubble" : "selection") << "\n";
    std::cout << std::setw(10) << "ref";
    std::cout << ": " << from.str() << "\n"; 
    std::cout << std::setw(10) << min_len;
    std::cout << ": " << min_str << "\n";
}

int main()
{
    permstock pb { {1, 2, 3, 4, 5, 6, 7, 8, 9} };
    std::vector<permstock> v;

    // populate possible solutions' vector
    do {
        if (satisfy(pb.perm)) {
            v.push_back(pb);
        }
    } while (std::next_permutation(pb.perm, pb.perm + 9));

    std::cout << "good permutations: " << v.size() << "\n";
    for (auto& p : v) {
        std::cout << p.str() << "; d1=" << calc_dist(p.perm, true) <<
            ", d2=" << calc_dist(p.perm, false) << "\n";
    }
    std::cout << "\n";
    
    calc(true, v);
    calc(false, v);

    return 0;
}