Sprawdzenie poprawności sudoku

Odpowiedz Nowy wątek
2018-08-21 23:46
0

Witam, właśnie jestem w trakcie rozwiązywania zadania ze SPOJ'a, podaję link https://pl.spoj.com/problems/SUDOKUC/.
Stworzyłam już funkcję sprawdzajaca kolumny i wiersze, ale nie mam pomysłu na funkcje, która sprawdzi kwadrat 3x3. Bardzo proszę o podpowiedź.

Pozostało 580 znaków

2018-08-21 23:49
kq
0

Pokaż kod.


Pozostało 580 znaków

2018-08-22 07:31
0

Jak na moje to utwórz 9 tablic po 9 elementów, dodaj do każdej odpowiednio kolumny 1-3/wiersze 1-3, potem 1-3/4-6 i tak dalej, i w tej tablicy sprawdzaj każdy element czy pojawił się gdzieś indziej w tej samej tablicy. Tak przynajmniej robiłem to ja, tyle że w Pythonie i na listach.

w Pythonie jest o tyle wygodnie, że można zastosować instrukcję typu len(lista)==len(set(lista)), która wychwyci czy są elementy powtarzające się... :) - hurgadion 2018-08-22 10:44
Dzięki za podpowiedź, chociaż chciałbym później jeszcze móc sprawdzić gdzie był błąd, ale faktycznie powinienem pomyśleć jak użyć setów do tego. - nEmoFizz 2018-08-22 11:29
no to jeżeli warunek nie jest spełniony... wtedy przeszukujemy określoną listę i szukamy niewłaściwych (tego powyższy warunek nie wychwytuje, np. dla zestawu [1, 2, 3, 4, 5, 6, 7, 8, 10]), ewentualnie zdublowanych warrtości... :) - hurgadion 2018-08-22 11:32

Pozostało 580 znaków

2018-08-22 10:46
1

Od czego ja bym zaczął:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <array>

const size_t SudokuSize = 9;
using Sudoku = std::array<std::array<int, SudokuSize>, SudokuSize>;

// TODO:
bool isCorrectSolution(const Sudoku &sudoku); 

void loadSudoku(std::istream &input, Sudoku &sudoku) {
     for (auto &row : sudoku) {
         std::copy_n(std::istream_iterator<Sudoku::value_type::value_type>(input), row.size(), row.begin());
     }
}

int main() {
    // duzo danych wejściowych
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
         Sudoku sudoku;
         loadSudoku(std::cin, sudoku);
         std::cout << (isCorrectSolution(sudoku) ? "TAK" : "NIE") << '\n';
    }

    return 0;
}

Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 2x, ostatnio: MarekR22, 2018-08-23 12:22
Czy ja wiem.. Niby najprostsze rozwiązanie ale wynik negatywny może być już po wczytaniu pierwszego wiersza. Wtedy pozostałe należy po prostu zignorować a nie wczytywać do pamięci. A sprawdzić 3 kwadraty można już po 3 wierszach. IMHO da się to zrobić przy mniejszej złożoności pamięciowej.. no ale niech od tego zacznie. - Mokrowski 2018-08-22 19:57
Z całym szacunkiem, ale najwyraźniej nie masz pojęcia co to jest złożoność. Złożoność pamięciowa mojego kodu jest o(1) czyli nie ma co optymalizować. Zresztą sam problem i dane wejściowe nie mają właściwości, które mają wpływ na złożoność algorytmu (tylko liczba przypadków testowych). Twoje rozważania zdecydowanie kwalifikują się jako "premature optimizations". - MarekR22 2018-08-22 22:13
Widać że mnie nie zrozumiałeś aczkolwiek mi to nie przeszkadza :) BTW, popraw kod bo zawiera błędy. Nawet jako przykład. - Mokrowski 2018-08-23 11:51
Twoje usprawnienia skomplikują program ponad miarę, a zysk nie będzie mierzalny. Na dodatek skupiasz się na najmniej istotnym warunkiem brzegowym. Radzę poczytać o tym czym jest "przedwczesna optymalizacja". A jeśli widzisz błąd to go wytknij, żebym mógł poprawić. - MarekR22 2018-08-23 12:04
Ok, zaimplementuję i sprawdzę. Jestem ciekaw jakie będą wyniki dla rozwiązania idącego torem który pokazałeś (podkreślam że nie jest błędny) i po tym jak nieco popracuję nad rozwiązaniem. Raczej przeczytałem czym jest przedwczesna optymalizacja. Myślę jednak że zawsze warto próbować innych rozwiązań jeśli zna się "kanoniczne". W zadaniu nie ma precyzji co do n. Ja zakładał bym std::size_t. Stałą chyba constexp. Raczej std::istream_iterator. Zamiast row.size() stałą. Raczej std::ios_base::sync_with_stdio. Ostatni return 0... jak wiadomo są dwie szkoły pisać/nie pisać :) - Mokrowski 2018-08-23 12:17
na wszelki wypadek przepuściłem przez kompilator. - MarekR22 2018-08-23 12:23

Pozostało 580 znaków

2018-08-23 17:15
0

No to podpowiedź:

  1. Oczywiście możesz w C++ użyć std::set i sprawdzić jego wielkość. Jeśli po dodaniu liczb do zbiorów dla wiersza, kolumny czy "pudełka 3x3" będzie miał długość inną niż 9, to oznacza że wiersz czy kolumna czy "pudełko" zawiera powtórzenia. Oczywiście przed każdym dodaniem liczby należy sprawdzić czy należy do przedziału [1, 9].

  2. Myślę że lepiej bo o wiele szybciej i oszczędniej co do pamięci, jest zauważyć że wystarczy przesunąć bit o wartość z danych testu i wykonać operację OR na masce. Zauważ że jeśli dla zbioru danych (1, 2, 3, 4, 5, 6, 7, 8, 9) wykonasz tę operację, w wyniku będzie 1022 bo jest to równe binarnie 0b1111111110. Każdą liczbę spoza zakresu, mapujesz na 0. Tu prosty kod uświadamiający jak to ma działać:

#include <iostream>
#include <vector>

bool is_value_in_range(int value) {
    return value > 0 && value < 10;
}

bool is_data_ok(const std::vector<int>& data) {
    auto mask = 0U;
    for(const auto& val: data) {
        mask |= 1 << (is_value_in_range(val) ? val: 0);
    }
    return mask == 1022U;
}

int main() {
    std::vector<int> ok_data{2,1,8,4,5,9,7,3,6};
    std::vector<int> not_ok_data1{1,7,3,4,5,6,7,8,9};
    std::vector<int> not_ok_data2{-100,1,8,4,5,9,7,3,6};

    for(const auto& data_ptr: {&ok_data, &not_ok_data1, &not_ok_data2}) {
        std::cout << (is_data_ok(*data_ptr) ? "OK": "NOT OK") << '\n';
    }
}

Ta implementacja jest o wiele szybsza niż korzystanie ze zbioru. Nawet dla zaledwie 9 wartości.


Każdy problem w informatyce można rozwiązać, dodając kolejny poziom pośredniości,z wyjątkiem problemu zbyt dużej liczby warstw pośredniości — David J. Wheeler
edytowany 1x, ostatnio: Mokrowski, 2018-08-23 17:15

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0