Sprawdzenie poprawności sudoku

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

0

Pokaż kod.

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.

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;
}
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.

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