Python, with Z3Py

# !pip install z3-solver
from z3 import *


def main():
    # Create variables P0 to P15
    P = [Int(f'P{i}') for i in range(16)]

    s = Solver()

    # Each variable is between 1 and 16
    for p in P:
        s.add(p >= 1, p <= 16)

    # All variables are distinct
    s.add(Distinct(P))

    # Add the sum constraints
    s.add(P[0] + P[1] + P[2] == 29)  # P0 + P1 + P2 = 29
    s.add(P[3] + P[4] + P[5] + P[6] == 29)  # P3 + P4 + P5 + P6 = 29
    s.add(P[9] + P[10] + P[11] + P[12] == 29)  # P9 + P10 + P11 + P12 = 29
    s.add(P[13] + P[14] + P[15] == 29)  # P13 + P14 + P15 = 29
    s.add(P[0] + P[6] + P[9] + P[15] == 29)  # P0 + P6 + P9 + P15 = 29
    s.add(P[2] + P[7] + P[11] == 29)  # P2 + P7 + P11 = 29
    s.add(P[4] + P[8] + P[13] == 29)  # P4 + P8 + P13 = 29

    count = 0
    while s.check() == sat:
        # print(f"{count=}")
        count += 1
        model = s.model()
        # Block the current solution
        s.add(Or([p != model[p] for p in P]))

    print(f"Number of solutions: {count}")


if __name__ == "__main__":
    main()

Number of solutions: 9368

C++ - 300 Milliseconds

Per request, I've added my own code to solve this puzzle. On my computer, it clocks in at an average of 0.310 seconds (310 milliseconds) but depending on variance can run as quickly as 287 milliseconds. I very rarely see it rise above 350 milliseconds, usually only if my system is bogged down with a different task.

These times are based on the self-reporting used in the program, but I also tested using an external timer and get similar results. Overhead in the program seems to add about 10 milliseconds.

Also, my code doesn't quite handle duplicates correctly. It can solve using them, but it doesn't eliminate "visually identical" solutions from the solution set.

#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 minutes

This kind of puzzle seems like a perfect use-case for Prolog. So, I coded up a solution in Prolog! Here it is:

:- 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.

Unfortunately, it's not as fast as I expected. Maybe someone more well-versed in declarative programming (or Prolog specifically) can offer some optimization tips. You can invoke the rule puzzle with the following command:

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)).

Try it out online here. You can substitute any number in place of the 29s in the code to generate all solutions. As it stands, all 29-solutions are found in approximately 30 seconds, so to find all possible solutions should be approximately 3 minutes.

C - near 0.5 sec

This very naive program give all the solutions in half a second on my 4 years old laptop. No multithread, no hashing.

Windows 10, Visual Studio 2010, CPU core I7 64 bit

Try online on 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);
}