Geschichte

Mein Unternehmen verschickt wöchentlich einen Newsletter an alle Mitarbeiter des Unternehmens. In diesen Newslettern ist ein Rätsel enthalten, zusammen mit einem Gruß an denjenigen im Unternehmen, der als erster eine E-Mail verschickt / eine Lösung für das Rätsel der letzten Woche bereitgestellt hat. Die meisten dieser Rätsel sind ziemlich trivial und ehrlich gesagt ziemlich langweilig für ein Technologieunternehmen, aber vor einigen Monaten gab es eines, das meine Aufmerksamkeit auf sich zog.

Das ursprüngliche Rätsel:

Angesichts der folgenden Form:

Sie haben die natürlichen Zahlen von 1 bis 16. Passen Sie sie alle in diese Form ein, sodass alle zusammenhängenden Zeilen und zusammenhängenden Spalten zusammen 29 ergeben.

Eine solche Lösung für dieses Rätsel (die "kanonische" Lösung, die ich dem Newsletter vorgelegt habe) war beispielsweise die folgende:

Im Verlauf der Lösung habe ich jedoch einige interessante Informationen gefunden:

• Es gibt deutlich mehr Lösungen als nur diese. Tatsächlich gibt es 9.368 Lösungen.
• Wenn Sie den Regelsatz so erweitern, dass nur Zeilen und Spalten gleich sind und nicht unbedingt 29, erhalten Sie 33.608 Lösungen:
  • 4.440 Lösungen für eine Summe von 27.
  • 7.400 Lösungen für eine Summe von 28.
  • 9.368 Lösungen für eine Summe von 29.
  • 6.096 Lösungen für eine Summe von 30.
  • 5.104 Lösungen für eine Summe von 31.
  • 1.200 Lösungen für eine Summe von 32.

Also machten ich und meine Mitarbeiter (obwohl größtenteils nur mein Manager, da er der einzige andere als ich mit Programmierkenntnissen für allgemeine Zwecke war) uns auf eine Herausforderung, die den größten Teil des Monats dauerte - wir hatten andere, tatsächliche Jobs. damit verbundene Verpflichtungen mussten wir erfüllen - um zu versuchen, ein Programm zu schreiben, das jede einzelne Lösung auf dem schnellstmöglichen Weg findet.

Ursprüngliche Statistik

Das allererste Programm, das ich geschrieben habe, um das Problem zu lösen, überprüfte einfach immer wieder zufällige Lösungen und hörte auf, als es eine Lösung fand. Wenn Sie eine mathematische Analyse zu diesem Problem durchgeführt haben, wissen Sie wahrscheinlich bereits, dass dies nicht hätte funktionieren sollen. Aber irgendwie hatte ich Glück und das Programm brauchte nur eine Minute, um eine einzige Lösung zu finden (die, die ich oben gepostet hatte). Wiederholte Durchläufe des Programms dauerten oft 10 oder 20 Minuten, so dass dies offensichtlich keine rigorose Lösung für das Problem war.

Ich wechselte zu einer rekursiven Lösung, die jede mögliche Veränderung des Puzzles durchlief, und verwarf viele Lösungen auf einmal, indem ich Summen eliminierte, die sich nicht summierten. Wenn die erste Zeile / Spalte, die ich gerade verglich, nicht gleich war, konnte ich sofort aufhören, diesen Zweig zu überprüfen, da ich wusste, dass nichts anderes, das in das Puzzle permutierte, dies ändern würde.

Mit diesem Algorithmus hatte ich den ersten "richtigen" Erfolg: Das Programm konnte in etwa 5 Minuten alle 33.608 Lösungen generieren und ausspucken.

Mein Manager verfolgte einen anderen Ansatz: Als er wusste, dass die einzig möglichen Lösungen Summen von 27, 28, 29, 30, 31 oder 32 enthielten, schrieb er eine Multithread-Lösung, die mögliche Summen nur für diese spezifischen Werte überprüfte. Er schaffte es, sein Programm in nur 2 Minuten zum Laufen zu bringen. Also iterierte ich noch einmal; Ich habe alle möglichen 3/4-stelligen Summen (zu Beginn des Programms; sie werden in der Gesamtlaufzeit gezählt) gehasht und die "Teilsumme" einer Zeile verwendet, um den verbleibenden Wert basierend auf einer zuvor abgeschlossenen Zeile nachzuschlagen, anstatt Testen aller verbleibenden Werte und Verkürzen der Zeit auf 72 Sekunden. Mit etwas Multithreading-Logik habe ich es dann auf 40 Sekunden gebracht. Mein Manager hat das Programm mit nach Hause genommen, einige Optimierungen an der Programmausführung vorgenommen und seine Geschwindigkeit auf 12 Sekunden gesenkt. Ich habe die Auswertung der Zeilen und Spalten neu angeordnet,

Das schnellste Programm, das einer von uns nach einem Monat erhielt, war für meinen Manager 0,15 Sekunden und für mich 0,33 Sekunden. Ich landete behauptet , dass mein Programm war schneller obwohl, da mein Manager Programm, während es tat finden alle Lösungen, druckte sie nicht in eine Textdatei aus. Wenn er diese Logik zu seinem Code hinzufügte, dauerte es oft mehr als 0,4 bis 0,5 Sekunden.

Wir haben unsere intrapersonale Herausforderung seitdem bestehen lassen, aber natürlich bleibt die Frage: Kann dieses Programm schneller gemacht werden?

Das ist die Herausforderung, die ich euch stellen werde.

Deine Herausforderung

Die Parameter, unter denen wir gearbeitet haben, haben die "Summe von 29" -Regel gelockert und sind stattdessen "alle Zeilen / Spalten gleich", und ich werde diese Regel auch für euch festlegen. Die Herausforderung lautet daher: Schreiben Sie ein Programm, das in kürzester Zeit alle Lösungen für dieses Rätsel findet (und druckt!). Ich werde eine Obergrenze für eingereichte Lösungen festlegen: Wenn das Programm auf einem relativ anständigen Computer (<8 Jahre alt) länger als 10 Sekunden dauert, ist es wahrscheinlich zu langsam, um gezählt zu werden.

Außerdem habe ich ein paar Boni für das Rätsel:

• Können Sie die Lösung so verallgemeinern, dass sie für jeden Satz von 16 Zahlen funktioniert, nicht nur für int[1,16]? Die Timing-Bewertung würde auf der Grundlage der ursprünglich festgelegten Eingabeaufforderungsnummer ausgewertet, jedoch über diesen Codepfad weitergeleitet. (-10%)
• Können Sie den Code so schreiben, dass er mit doppelten Zahlen ordnungsgemäß umgeht und diese auflöst? Dies ist nicht so einfach, wie es scheint! Lösungen, die "visuell identisch" sind, sollten in der Ergebnismenge eindeutig sein. (-5%)
• Kannst du mit negativen Zahlen umgehen? (-5%)

Sie können auch versuchen , eine Lösung zu generieren, die mit Gleitkommazahlen umgehen kann. Lassen Sie sich jedoch nicht schockieren, wenn dies völlig fehlschlägt. Wenn Sie jedoch eine robuste Lösung finden, ist dies möglicherweise einen großen Bonus wert!

In jeder Hinsicht gelten "Rotationen" als einzigartige Lösungen. Eine Lösung, bei der es sich nur um eine Rotation einer anderen Lösung handelt, gilt als ihre eigene Lösung.

Die IDEs, mit denen ich auf meinem Computer arbeite, sind Java und C ++. Ich kann Antworten aus anderen Sprachen akzeptieren, aber Sie müssen möglicherweise auch einen Link angeben, über den ich eine einfach einzurichtende Laufzeitumgebung für Ihren Code erhalten kann.

C - in der Nähe von 0,5 s

Dieses sehr naive Programm gibt alle Lösungen in einer halben Sekunde auf meinem 4 Jahre alten Laptop. Kein Multithread, kein Hashing.

Windows 10, Visual Studio 2010, CPU-Kern I7 64 Bit

Versuchen Sie es online auf ideone

#include <stdio.h>
#include <time.h>

int inuse[16];
int results[16+15+14];

FILE *fout;

int check(int number)
{
    if (number > 0 && number < 17 && !inuse[number-1])
    {
        return inuse[number-1]=1;
    }
    return 0;
}

void free(int number)
{
    inuse[number-1]=0;
}

void out(int t, int* p)
{
    int i;
    fprintf(fout, "\n%d",t);
    for(i=0; i< 16; i++) fprintf(fout, " %d",*p++);
}

void scan() 
{
    int p[16];
    int t,i;
    for (p[0]=0; p[0]++<16;) if (check(p[0]))
    {
        for (p[1]=0; p[1]++<16;) if (check(p[1]))
        {
            for (p[2]=0; p[2]++<16;) if (check(p[2]))
            {
                t = p[0]+p[1]+p[2]; // top horiz: 0,1,2
                for (p[7]=0; p[7]++<16;) if (check(p[7]))
                {
                    if (check(p[11] = t-p[7]-p[2])) // right vert: 2,7,11
                    {
                        for(p[9]=0; p[9]++<16;) if (check(p[9]))
                        {
                            for (p[10]=0; p[10]++<16;) if (check(p[10]))
                            {
                                if (check(p[12] = t-p[9]-p[10]-p[11])) // right horiz: 9,10,11,12
                                {
                                    for(p[6]=0; p[6]++<16;) if (check(p[6]))
                                    {
                                        if (check(p[15] = t-p[0]-p[6]-p[9])) // middle vert: 0,6,9,15
                                        {
                                            for(p[13]=0; p[13]++<16;) if (check(p[13]))
                                            {
                                                if (check(p[14] = t-p[13]-p[15])) // bottom horiz:  13,14,15
                                                {
                                                    for(p[4]=0; p[4]++<16;) if (check(p[4]))
                                                    {
                                                        if (check(p[8] = t-p[4]-p[13])) // left vert: 4,8,13
                                                        {
                                                            for(p[3]=0; p[3]++<16;) if (check(p[3]))
                                                            {
                                                                if (check(p[5] = t-p[3]-p[4]-p[6])) // left horiz: 3,4,5,6
                                                                {
                                                                    ++results[t];
                                                                    out(t,p);
                                                                    free(p[5]);
                                                                }
                                                                free(p[3]);
                                                            }
                                                            free(p[8]);
                                                        }
                                                        free(p[4]);
                                                    }
                                                    free(p[14]);
                                                }
                                                free(p[13]);
                                            }
                                            free(p[15]);
                                        }
                                        free(p[6]);
                                    }
                                    free(p[12]);
                                }
                                free(p[10]);
                            }
                            free(p[9]);
                        }
                        free(p[11]);
                    }
                    free(p[7]);
                }    
                free(p[2]);
            } 
            free(p[1]);
        }
        free(p[0]);
    }
    for(i=0;i<15+16+14;i++)
    {
        if(results[i]) printf("%d %d\n", i, results[i]);
    }
}

void main()
{
    clock_t begin, end;
    double time_spent;
    begin = clock();

    fout = fopen("c:\\temp\\puzzle29.txt", "w");
    scan();
    fclose(fout);

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("Time %g sec\n", time_spent);
}

C ++ - 300 Millisekunden

Auf Wunsch habe ich meinen eigenen Code hinzugefügt, um dieses Rätsel zu lösen. Auf meinem Computer dauert die Taktung durchschnittlich 0,310 Sekunden (310 Millisekunden), kann jedoch je nach Abweichung bis zu 287 Millisekunden dauern. Ich sehe es sehr selten über 350 Millisekunden ansteigen, normalerweise nur, wenn mein System mit einer anderen Aufgabe überfordert ist.

Diese Zeiten basieren auf der im Programm verwendeten Selbstmeldung, ich habe sie jedoch auch mit einem externen Timer getestet und erhalte ähnliche Ergebnisse. Der Overhead im Programm scheint etwa 10 Millisekunden hinzuzufügen.

Auch dann , wenn mein Code nicht ganz Duplikate korrekt verarbeiten. Es kann mit ihnen gelöst werden, aber es werden keine "visuell identischen" Lösungen aus dem Lösungssatz entfernt.

#include<iostream>
#include<vector>
#include<random>
#include<functional>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<thread>
#include<chrono>
#include<fstream>
#include<iomanip>
#include<string>
#include<mutex>
#include<queue>
#include<sstream>
#include<utility>
#include<atomic>
#include<algorithm>

//#define REDUCE_MEMORY_USE

typedef std::pair<int, std::vector<std::pair<int, int>>> sumlist;
typedef std::unordered_map<int, std::vector<std::pair<int, int>>> summap;
typedef std::array<int, 16> solution_space;

class static_solution_state {
public:
    std::array<int, 16> validNumbers;
    summap twosums;
    size_t padding;
    std::string spacing;

    static_solution_state(const std::array<int, 16> & _valid);

    summap gettwovaluesums();
    std::vector<sumlist> gettwovaluesumsvector();
};

static_solution_state::static_solution_state(const std::array<int, 16> & _valid) 
    : validNumbers(_valid) {
    twosums = gettwovaluesums();
    padding = 0;
    for (int i = 0; i < 16; i++) {
        size_t count = std::to_string(validNumbers[i]).size();
        if (padding <= count) padding = count + 1;
    }
    spacing.resize(padding, ' ');
}

class solution_state {
private:
    const static_solution_state * static_state;
public:
    std::array<int, 16> currentSolution;
    std::array<bool, 16> used;
    std::array<int, 7> sums;
    size_t solutions_found;
    size_t permutations_found;
    size_t level;
    std::ostream * log;

    solution_state(const static_solution_state & _sstate);
    solution_state(static_solution_state & _sstate) = delete;
    void setLog(std::ostream & out);
    const int & operator[](size_t index) const;

};

solution_state::solution_state(const static_solution_state & _sstate) {
    static_state = &_sstate;
    sums = { 0 };
    used = { false };
    currentSolution = { -1 };
    solutions_found = 0;
    permutations_found = 0;
    level = 0;
}

void solution_state::setLog(std::ostream & out) {
    log = &out;
}

const int & solution_state::operator[](size_t index) const {
    return static_state->validNumbers[currentSolution[index]];
}

int getincompletetwosum(const static_solution_state & static_state, const solution_state & state);
void permute(const static_solution_state & static_state, solution_state & state, volatile bool & reportProgress, const volatile size_t & total_tests, volatile bool & done);
void setupOutput(std::fstream & out);
void printSolution(const static_solution_state & static_state, const solution_state & state);
constexpr size_t factorial(const size_t iter);

const bool findnext2digits[16]{
    false, false, false,
    true, false,
    false, true, false,
    true, false,
    true, false,
    true, false,
    true, false
};

const int currentsum[16]{
    0, 0, 0,
    1, 1,
    2, 2, 2,
    3, 3,
    4, 4,
    5, 5,
    6, 6
};

const int twosumindexes[7][2]{
    { 0, -1},
    { 2, -1},
    { 5, -1},
    { 5, -1},
    { 0,  7},
    { 11, 4},
    { 10, 9}
};

const std::array<size_t, 17> facttable = [] {
    std::array<size_t, 17> table;
    for (int i = 0; i < 17; i++) table[i] = factorial(i);
    return table;
}();

const int adj = 1;

std::thread::id t1id;

int main(int argc, char** argv) {
    //std::ios_base::sync_with_stdio(false);
    std::array<int, 16> values = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 };
    if (argc == 17) {
        for (int i = 0; i < 16; i++) {
            values[i] = atoi(argv[i + 1]);
        }
    }
    auto start = std::chrono::high_resolution_clock::now();
    const static_solution_state static_state(values);
#if defined(REDUCE_MEMORY_USE)
    const int num_of_threads = max(1u, min(thread::hardware_concurrency(), 16u));
#else
    const int num_of_threads = 16;
#endif
    std::vector<solution_state> states(num_of_threads, static_state);
    for (int i = 0; i < num_of_threads; i++) {
        int start = i * 16 / num_of_threads;
        states[i].permutations_found += start * factorial(16) / 16;
    }
    std::fstream out;
    setupOutput(out);
    std::locale loc("");
    std::cout.imbue(loc);
    volatile bool report = false;
    volatile bool done = false;
    volatile size_t tests = 0;

    std::thread progress([&]() {
        auto now = std::chrono::steady_clock::now();
        while (!done) {
            if (std::chrono::steady_clock::now() - now > std::chrono::seconds(1)) {
                now += std::chrono::seconds(1);

                size_t t_tests = 0;
                for (int i = 0; i < num_of_threads; i++) t_tests += states[i].permutations_found - i * factorial(16) / num_of_threads;
                tests = t_tests;
                report = true;
            }
            std::this_thread::yield();
        }
    });

    if (num_of_threads <= 1) {


        states[0].setLog(out);
        permute(static_state, states[0], report, tests, done);


    } 
    else {
        std::vector<std::thread> threads;
#if defined(REDUCE_MEMORY_USE)
        std::vector<std::fstream> logs(num_of_threads);
#else
        std::vector<std::stringstream> logs(num_of_threads);
#endif
        for (int i = 0; i < num_of_threads; i++) {
            threads.emplace_back([&, i]() {
                if (i == 0) t1id = std::this_thread::get_id();
                int start = i * 16 / num_of_threads;
                int end = (i + 1) * 16 / num_of_threads;
#if defined(REDUCE_MEMORY_USE)
                logs[i].open("T"s + to_string(i) + "log.tmp", ios::out);
#endif
                logs[i].imbue(loc);
                states[i].setLog(logs[i]);

                for (int j = start; j < end; j++) {


                    states[i].currentSolution = { j };
                    states[i].level = 1;
                    states[i].used[j] = true;
                    permute(static_state, states[i], report, tests, done);


                }
            });
        }

        std::string buffer;
        for (int i = 0; i < num_of_threads; i++) {
            threads[i].join();
#if defined(REDUCE_MEMORY_USE)
            logs[i].close();
            logs[i].open("T"s + to_string(i) + "log.tmp", ios::in);
            logs[i].seekg(0, ios::end);
            auto length = logs[i].tellg();
            logs[i].seekg(0, ios::beg);
            buffer.resize(length);
            logs[i].read(&buffer[0], length);
            logs[i].close();
            remove(("T"s + to_string(i) + "log.tmp").c_str());
            out << buffer;
#else
            out << logs[i].str();
#endif
        }
    }
    done = true;
    out.close();

    if (num_of_threads > 1) {
        size_t t_tests = 0;
        for (int i = 0; i < num_of_threads; i++) t_tests += states[i].permutations_found - i * factorial(16) / num_of_threads;
        tests = t_tests;
    }

    size_t solutions = 0;
    for (const auto & state : states) {
        solutions += state.solutions_found;
    }

    auto end = std::chrono::high_resolution_clock::now();

    progress.join();

    auto duration = end - start;
    auto secondsDuration = std::chrono::duration_cast<std::chrono::milliseconds>(duration);
    std::cout << "Total time to process all " << tests << " results: " << std::setprecision(3) << std::setiosflags(std::ostream::fixed) << (secondsDuration.count()/1000.0) << "s" << "\n";
    std::cout << "Solutions found: " << solutions << std::endl;
    //system("pause");
    return 0;
}

void permute(const static_solution_state & static_state, solution_state & state, volatile bool & reportProgress, const volatile size_t & total_tests, volatile bool & done) {
    if (done) return;
    if (state.level >= 16) {
        if (reportProgress) {
            reportProgress = false;
            std::cout << "Current Status:" << "\n";
            std::cout << "Test " << total_tests << "\n";
            std::cout << "Contents: {";
            for (int i = 0; i < 15; i++) std::cout << std::setw(static_state.padding - 1) << state[i] << ",";
            std::cout << std::setw(static_state.padding - 1) << state[15] << "}" << "(Partial Sum: " << state.sums[0] << ")" << "\n";
            std::cout << "=====================" << "\n";
        }
        printSolution(static_state,state);
        state.solutions_found++;
        state.permutations_found++;
    }
    else {
        if (state.level == 3) state.sums[0] = state[0] + state[1] + state[2];

        if (!findnext2digits[state.level]) {
            for (int i = 0; i < 16; i++) {
                if (!state.used[i]) {
                    state.currentSolution[state.level] = i;
                    state.used[i] = true;
                    state.level++;
                    permute(static_state, state, reportProgress, total_tests, done);
                    state.level--;
                    state.used[i] = false;
                }
            }
        }
        else {
            int incompletetwosum = getincompletetwosum(static_state, state);
            if (static_state.twosums.find(incompletetwosum) == static_state.twosums.end()) {
                state.permutations_found += facttable[16 - state.level];
            }
            else {
                size_t successes = 0;
                const std::vector<std::pair<int, int>> & potentialpairs = static_state.twosums.at(incompletetwosum);
                for (const std::pair<int, int> & values : potentialpairs) {
                    if (!state.used[values.first] && !state.used[values.second]) {
                        state.currentSolution[state.level] = values.first;
                        state.currentSolution[state.level + 1] = values.second;
                        state.used[values.first] = true;
                        state.used[values.second] = true;
                        state.level += 2;
                        permute(static_state, state, reportProgress, total_tests, done);
                        state.level -= 2;
                        state.used[values.first] = false;
                        state.used[values.second] = false;

                        successes++;
                    }
                }
                state.permutations_found += facttable[16 - state.level - 2] * ((16 - state.level) * (15 - state.level) - successes); 
            }
        }
    }
}

int getincompletetwosum(const static_solution_state & static_state, const solution_state & state) {
    int retvalue = state.sums[0];
    int thissum = currentsum[state.level];
    for (int i = 0; i < 2 && twosumindexes[thissum][i] >= 0; i++) {
        retvalue -= state[twosumindexes[thissum][i]];
    }
    return retvalue;
}

constexpr size_t factorial(size_t iter) {
    return (iter <= 0) ? 1 : iter * factorial(iter - 1);
}

void setupOutput(std::fstream & out) {
    out.open("puzzle.txt", std::ios::out | std::ios::trunc);
    std::locale loc("");
    out.imbue(loc);
}

void printSolution(const static_solution_state & static_state, const solution_state & state) {
    std::ostream & out = *state.log;
    out << "Test " << state.permutations_found << "\n";
    static const auto format = [](std::ostream & out, const static_solution_state & static_state, const solution_state & state, const std::vector<int> & inputs) {
        for (const int & index : inputs) {
            if (index < 0 || index >= 16) out << static_state.spacing;
            else out
                << std::setw(static_state.padding)
                << state[index];
        }
        out << "\n";
    };
    format(out, static_state, state, { -1, -1, -1,  0,  1,  2 });
    format(out, static_state, state, { 15,  9, 14, 10, -1,  3 });
    format(out, static_state, state, { -1,  8, -1, 11, 12,  4, 13 });
    format(out, static_state, state, { -1,  5,  6,  7});

    out << "Partial Sum: " << (state.sums[0]) << "\n";
    out << "=============================" << "\n";
}

summap static_solution_state::gettwovaluesums() {
    summap sums;
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) {
            if (i == j) continue;
            std::pair<int,int> values( i, j );
            int sum = validNumbers[values.first] + validNumbers[values.second];
            sums[sum].push_back(values);
        }
    }
    return sums;
}

std::vector<sumlist> static_solution_state::gettwovaluesumsvector() {
    std::vector<sumlist> sums;
    for (auto & key : twosums) {
        sums.push_back(key);
    }

    std::sort(sums.begin(), sums.end(), [](sumlist a, sumlist b) {
        return a.first < b.first;
    });
    return sums;
}

Prolog - 3 Minuten

Diese Art von Puzzle scheint ein perfekter Anwendungsfall für Prolog zu sein. Also habe ich in Prolog eine Lösung programmiert! Hier ist es:

:- use_module(library(clpfd)).

puzzle(P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15) :-
    Vars = [P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15],
    Vars ins 1..16,
    all_different(Vars),
    29 #= P0 + P1 + P2,
    29 #= P3 + P4 + P5 + P6,
    29 #= P9 + P10 + P11 + P12,
    29 #= P13 + P14 + P15,
    29 #= P0 + P6 + P9 + P15,
    29 #= P2 + P7 + P11,
    29 #= P4 + P8 + P13.

Leider ist es nicht so schnell wie ich erwartet hatte. Vielleicht kann jemand, der sich mit deklarativer Programmierung (oder speziell mit Prolog) auskennt, einige Optimierungstipps anbieten. Sie können die Regel puzzlemit dem folgenden Befehl aufrufen :

time(aggregate_all(count, (puzzle(P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15), labeling([leftmost, up, enum], [P9, P15, P13, P0, P4, P2, P6, P11, P1, P5, P3, P7, P14, P12, P10, P8])), Count)).

Probieren Sie es hier online aus . Sie können eine beliebige Zahl anstelle des 29s im Code einsetzen, um alle Lösungen zu generieren. So wie es aussieht, werden alle 29-Lösungen in ungefähr 30 Sekunden gefunden. Um alle möglichen Lösungen zu finden, sollten Sie ungefähr 3 Minuten brauchen.