Mistrz matematyki - klasa 4 szkoła podstawowa

Hej,

mam zadanie jak w temacie, poniżej treść:

"Liczba jest podzielna przez 11. Wtedy, gdy sumując co drugą cyfrę, otrzymujemy w obydwu przypadkach to samo. Np., dla liczby 5841 mamy 5+4=8+1.
Rozmieść podane niżej cyfry w kwadracie (kwadrat 4x4) w taki sposób, żeby powstałe liczby czterocyfrowe, czytane poziomo i pionowo, w przód i wspak, były podzielne przez 11.
0,1,1,2,2,3,3,4,5,6,7,8,8,8,9,9.".

Chciałbym to rozwiązać za pomocą c++,c#, pl/sql(może by było prościej?) - nieważne. Generalnie, pytanie brzmi: jak napisać algorytm?

Początkowo próbowałem za pomocą tablicy dwuwymiarowej [4,4].
Później pomyślałem, że zrobię to za pomocą tablicy jednowymiarowej i odpowiednio posortuję ciąg podanych cyfr (kolejna cyfra-> kolejny pole w kwadracie).
Jeżeli poniższy warunek będzie spełniony, wówczas mamy posortowany ciąg cyfr(zadanie rozwiązane): podane poniżej liczby to indeksy tablicy jednowymiarowej:
0+2=1+3 & 4+6=5+7 & 8+10=9+11 & 12+14=13+15 & 0+8=4+12 & 1+9=5+13 & 2+10=6+14 & 3+11=7+15

wg mnie jest to wyzwanie. Może ktoś coś podpowie bądź znajdzie rozwiązanie? ;)

Ale tak zupełnie najprosciej chcesz to rozwiązać? Ja bym załadował do solvera constraint programmingu /smt solvera, bo to jest klasyczny przykład na programowanie z ograniczeniami. Jeśli oznaczymy kolejne pola w tablicy literkami to zaraz mamy równania:

a+c = b+d
e+g = f+h
i+k = j+l
m+o = n+p

a+i = e+m
b+j = f+n
c+k = g+o
d+l = h+p

I teraz wiemy dodatkowo że każda literka może być 0-9 i każda suma 0-18. Oczywście potencjalnych rozwiązań będzie cała masa, bo nie trudno zauważyć, że możemy np. wymienić kolumny/wiersze które są parowane i rozwiązanie nadal będzie działać.

Czytaj np. http://ericpony.github.io/z3py-tutorial/guide-examples.htm

Czy to jedna z tych zagadek dla której nie ma rozwiązania?

Dziękuje pięknie za podpowiedź Shalom, spróbuje użyć smt solvera. Patrząc na niego, przypomina mi się przesławny R.

Mi to wygląda na sudoku i ja bym to zrobił inaczej:

Wszystkie kombinacje 4 liczb ze zbioru 16 - 16 * 15 * 14 * 13 lub 16!/(16-4)!
Teraz wyszukać wszystkie podzielne przez 11 - to co szalom pokazał.
Teraz wybierasz jakąś liczbę ze zbioru i przelatujesz każdą liczbę i szukasz dla niej w zbiorze liczby tak zaczynającej potem tak zaczynającej i drugiej, potem tak zaczynającej i trzeciej, i potem tak zaczynającej i czwartej.

J0ras napisał(a):

Teraz wybierasz jakąś liczbę ze zbioru i przelatujesz każdą liczbę i szukasz dla niej w zbiorze liczby tak zaczynającej potem tak zaczynającej i drugiej, potem tak zaczynającej i trzeciej, i potem tak zaczynającej i czwartej.

Nie rozumiem tego, zobrazuj to proszę

Brutalne i dalekie od optymalnego rozwiązanie:

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>

inline void showSolution(const std::vector<int>& values) {
    std::cout << "+-+-+-+-+";

    for(size_t i = 0; i < values.size(); ++i) {
        bool newRow = !(i % 4);
        std::cout << (newRow ? "\n|" : "") << values[i] << '|';
    }

    std::cout << "\n+-+-+-+-+\n";
}

inline bool checkRows(const std::vector<int>& v) {
    bool answer = true;

    for(size_t i = 0; i < 16; i += 4) {
        if((v[i] + v[i + 2]) != (v[i + 1] + v[i + 3])) {
            answer = false;
            break;
        }
    }

    return answer;
}

inline bool checkColumns(const std::vector<int>& v) {
    bool answer = true;

    for(size_t i = 0; i < 4; ++i) {
        if((v[i] + v[i + 8]) != (v[i + 4] + v[i + 12])) {
            answer = false;
            break;
        }
    }

    return answer;
}

inline bool checkCondition(const std::vector<int>& values) {
    return checkRows(values) && checkColumns(values);
}

inline void showProgress(unsigned long long solutionCounter) {
    std::cout << std::string(40, '=') << "\nSolution: "
        << solutionCounter << '\n' << std::string(40, '=') << '\n';
}

int main() {
    std::vector<int> values = {0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 9, 9};
    unsigned long long solutionCounter = 0;

    do {
        if(checkCondition(values)) {
            ++solutionCounter;
            showProgress(solutionCounter);
            showSolution(values);
        }
    } while(std::next_permutation(values.begin(), values.end()));
}

Nie optymalizowałem specjalnie bo algorytm w takiej postaci się nie kwalifikuje do tego zabiegu. Raczej napisane "dla rozrywki" :-) Warto zobaczyć jak wolno taka 'czołgowa metoda" szuka.

PS. Poprawiona mała pomyłka w kodzie.... Rozwiązań jest 4096 i na mojej maszynie liczy ~16 min.

"Liczba jest podzielna przez 11. Wtedy, gdy sumując co drugą cyfrę, otrzymujemy w obydwu przypadkach to samo. Np., dla liczby 5841 mamy 5+4=8+1."
Nie jest to cała prawda. Jeśli mamy czterocyfrową liczbę (c1, c2, c3, c4) to warunkiem podzielności przez 11 jest podzielność wyniku c1 - c2 + c3 - c4 przez 11.
Przykładowo 8294, 8 - 2 + 9 - 4 = 11 jest podzielna przez 11, ale nie spełnia warunku 8+9==2+4.

Pierwszym krokiem może być wyznaczenie wszystkich "czwórek" podzielnych przez 11.

>>> a = [0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 8, 8, 9, 9]
>>> z = set((x1, x2, x3, x4) for x1, x2, x3, x4 in itertools.permutations(a, 4) if (x1 - x2 + x3 - x4) % 11 == 0)
>>> len(z)
680
>>> pprint.pprint(list(z)[:20])
[(0, 7, 2, 6),
 (7, 3, 5, 9),
 (7, 1, 0, 6),
 (4, 8, 7, 3),
 (3, 8, 0, 6),
 (5, 7, 6, 4),
 (0, 4, 5, 1),
 (3, 0, 9, 1),
 (7, 6, 0, 1),
 (7, 3, 1, 5),
 (8, 5, 1, 4),
 (9, 4, 0, 5),
 (4, 6, 3, 1),
 (8, 1, 4, 0),
 (6, 5, 8, 9),
 (8, 1, 0, 7),
 (3, 2, 6, 7),
 (8, 8, 3, 3),
 (9, 6, 8, 0),
 (9, 4, 7, 1)]

Dzięki za kod Mokrowski. Dobra robota -wyniki zgadzają się jak w mordę. Jestem wdzięczny i doceniam ;)