abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
    dnes 20:44 | Nová verze

    Svobodný a otevřený multiplatformní editor EPUB souborů Sigil (Wikipedie, GitHub) byl vydán ve verzi 2.5.0. Stejně tak doprovodný vizuální EPUB XHTML editor PageEdit (GitHub).

    Ladislav Hagara | Komentářů: 0
    dnes 12:22 | IT novinky

    Na základě národního atribučního procesu vláda České republiky označila Čínskou lidovou republiku za zodpovědnou za škodlivou kybernetickou kampaň proti jedné z neutajovaných komunikačních sítí Ministerstva zahraničních věcí ČR. Tato škodlivá aktivita, která trvala od roku 2022 a zasáhla instituci zařazenou na seznam české kritické infrastruktury, byla provedena kyberšpionážní skupinou APT31, veřejně spojovanou se zpravodajskou službou Ministerstvo státní bezpečnosti (MSS).

    Ladislav Hagara | Komentářů: 15
    dnes 00:11 | Nová verze

    Google Chrome 137 byl prohlášen za stabilní. Nejnovější stabilní verze 137.0.7151.55 přináší řadu novinek z hlediska uživatelů i vývojářů. Podrobný přehled v poznámkách k vydání. Opraveno bylo 11 bezpečnostních chyb. Vylepšeny byly také nástroje pro vývojáře.

    Ladislav Hagara | Komentářů: 1
    včera 19:22 | Nová verze

    Byl vydán AlmaLinux OS 10 s kódovým názvem Purple Lion. Podrobnosti v poznámkách k vydání. Na rozdíl od Red Hat Enterprise Linuxu 10 nadále podporuje x86-64-v2.

    Ladislav Hagara | Komentářů: 1
    včera 15:11 | Nová verze

    Byl vydán Mozilla Firefox 139.0. Přehled novinek v poznámkách k vydání a poznámkách k vydání pro vývojáře. Řešeny jsou rovněž bezpečnostní chyby. Nový Firefox 139 je již k dispozici také na Flathubu a Snapcraftu.

    Ladislav Hagara | Komentářů: 8
    včera 10:44 | Komunita

    Byly publikovány výsledky průzkumu mezi uživateli Blenderu uskutečněného v říjnu 2024. Zúčastnilo se více než 7000 uživatelů. Téměř 93 % z nich například používá uživatelské rozhraní v angličtině.

    Ladislav Hagara | Komentářů: 16
    26.5. 23:55 | Zajímavý článek

    Lukáš Růžička v článku RamaLama aneb vyháníme lamy na vlastní louku na MojeFedora.cz představuje open source nástroj RamaLama umožňující spouštět jazykové modely v izolovaných OCI kontejnerech, a to bezpečně, bez potřeby mít root přístup k počítači, s podporou GPU či CPU a bez zbytečných obtížností kolem.

    Ladislav Hagara | Komentářů: 1
    26.5. 22:55 | Nová verze

    Byl vydán Sublime Text 4 Build 4200. Sublime Text (Wikipedie) je proprietární multiplatformní editor textových souborů a zdrojových kódů. Ke stažení a k vyzkoušení je zdarma. Pro další používání je nutná licence v ceně 99 dolarů. Spolu se Sublime Merge je cena 168 dolarů.

    Ladislav Hagara | Komentářů: 0
    26.5. 18:00 | Nová verze

    Multiplatformní open source voxelový herní engine Luanti byl vydán ve verzi 5.12.0. Podrobný přehled novinek v changelogu. Původně se jedná o Minecraftem inspirovaný Minetest v říjnu loňského roku přejmenovaný na Luanti.

    Ladislav Hagara | Komentářů: 0
    26.5. 16:11 | Nová verze

    Armbian, tj. linuxová distribuce založená na Debianu a Ubuntu optimalizovaná pro jednodeskové počítače na platformě ARM a RISC-V, ke stažení ale také pro Intel a AMD, byl vydán ve verzi 25.5. Přehled novinek v Changelogu.

    Ladislav Hagara | Komentářů: 0
    Jaký je váš oblíbený skriptovací jazyk?
     (55%)
     (31%)
     (8%)
     (3%)
     (0%)
     (0%)
     (3%)
    Celkem 149 hlasů
     Komentářů: 12, poslední dnes 18:42
    Rozcestník

    Dotaz: Sudoku backtraking

    16.2.2014 16:02 Oxydentist
    Sudoku backtraking
    Přečteno: 430×
    Zdravim a prosím o radu. Dělám program, který by měl vygenerovat kompletní sudoku (neřeší zadané, ale do prázdného pole 9x9 nahází podle pravidel sudoku čísla). Důležitou pomůcku tvoří seznam povolených hodnot pro konkrétní políčko, čísla 1..9 Chtěl bych to řešit rekurzí, volá se po políčkách:

    1. Zkontroluju jestli zbývá nějaká povolená hodnota. Pokud ano : goto 2. Jinak: dopolním povolené hodnoty na 1..9 a vrátím se o políčko zpět.
    2. Náhodně vyberu číslo ze seznamu potenciálních hodnot.
    3. Zkontroluju jestli tato hodnota na tomto políčku netvoří kolizi s pravidly. Netvoří kolizi : goto 4, jinak goto5
    4. Je-li vše v pořádku, hodnotu použiju a vyškrtnu ji ze seznamu povolených hodnot pro toto políčko. Zavolám fci znova pro další políčko
    5. Tvoří-li kolizi, políčko vyškrtnu ze seznamu povolených hodnot a goto 1.

    To je tedy hlavní myšlenka, které jsem se snažil držet při tvoření následujícího kódu. Po prvním zpuštění, mi opravdu vytvořil pole čísel 9x9, které odpovídalo pravidlům sudoku. Z mně nepochopitelných důvodů - asi jsem musel něco omylem změnit - při každém dalším pokusu většinou vplní pouze pár řádků/sloupců a ve zbytku zůstanou nuly. Nejsem schopen najít chybu, zvláště když už mám opravdu jedno řešení hotové...

    Zdroják je kdyžtak k nahlédnutí na (omlouvám se za odkaz ven): http://programujte.com/forum/vlakno/26538-sudoku-backtraking/
    Předem díky za jakékoliv rady, postřehy a připomínky k logickému postupu nebo zdrojáku.

    Odpovědi

    16.2.2014 22:37 Thyrst' | skóre: 6 | blog: a256
    Rozbalit Rozbalit vše Re: Sudoku backtraking

    Řádka if (sudoku[9,9] <> 0) then je špatně. Nevím proč porovnáváš pomocí <>, když hodnota nemůže být záporná, stačí >. Jinak pro takové porovnání musíš převést sudoku[9,9] na číslo. Zkus if (int(sudoku[9,9]) > 0), tohle ti snad bude fungovat (soubor reseni.txt se vůbec nevytvoří, když je poslední políčko rovno 0).

    19.2.2014 12:40 Andrej | skóre: 51 | blog: Republic of Mordor
    Rozbalit Rozbalit vše Re: Sudoku backtraking

    Postupy tohoto typu mi připadějí poněkud na šavli:

    for k := e to kanpol[10]-1 do   {zakaz policko}
                        begin
                             kanpol[k] := kanpol[k+1];
                        end;
    

    Těžko říct, jestli je horší to neustálé procházení a přepisování pole nebo nadužívání magických konstant. Chybu bych v celém tom kódu asi v dohledné době nenašel, protože odporný jazyk zvaný Packal jsem už notnou dobu nepoužíval.

    Místo toho jsem si jen tak pro legraci před chvílí nějaké Sudoku naprogramoval. Pořádně jsem ho netestoval, takže není vůbec jisté, že negeneruje nesmysly. :-) Algoritmus je založený na Dancing Links, které popisuje Donald Knuth ve svém legendárním článku. Triviálně se dá přepnout na jiný typ Sudoku, třeba 2x2 nebo 4x4. Stačí jenom změnit konstantu SIDE. Snadno se taky dá tento generátor Sudoku upravit na řešítko Sudoku, které vypíše všechna řešení, existují-li nějaká. Stačí načíst zadání, hodnoty zafixovaných políček zvolit pomocí Listing::hide() (což sice obnáší průchod jedním celým spojákem u každého políčka, ovšem každým jenom jednou) a pak spustit na takto upravené datové struktuře celý algoritmus. Zdá se, že všech 288 existujících Sudoku typu 2x2 mi to generuje správně. V případě 3x3 nebo 4x4 bych se hodně načekal. ;-)

    #include <iostream>
    #include <type_traits>
    #include <iomanip>
    #include <new>
    
    static const size_t
        SIDE = 3,
        SIDE_2 = SIDE * SIDE,
        SIDE_4 = SIDE_2 * SIDE_2;
    
    static const size_t
        FILL = (10 + SIDE_2) / 10 + 1;
    
    class Assignment;
    class Listing;
    class Field;
    class Tile;
    class Row;
    class Column;
    class Board;
    
    class Listing {
    protected:
        Assignment    *fieldPrev;
        Assignment    *fieldNext;
        Assignment    *tilePrev;
        Assignment    *tileNext;
        Assignment    *rowPrev;
        Assignment    *rowNext;
        Assignment    *columnPrev;
        Assignment    *columnNext;
    
        inline operator Assignment *();
        inline void discard();
    
    public:
        inline Listing();
        inline Listing(Field &field, Tile &tile, Row &row, Column &column);
        inline Assignment* prev() const;
        inline Assignment* next() const;
        inline ~Listing();
    };
    
    class Assignment : public Listing {
        Assignment        *hidingOrder;
        const size_t    value;
    
        inline void fieldHide(Assignment **order);
        inline void fieldShow();
    
    public:
        inline Assignment(Field &field, Tile &tile, Row &row, Column &column, size_t value_);
        inline operator size_t() const;
        inline void hide(Assignment **order);
        inline void show(Assignment *order);
    };
    
    class Field : public Listing {
        size_t    value;
    
    public:
        inline Field(Tile (&tile)[SIDE_2], Row (&row)[SIDE_2], Column (&column)[SIDE_2]);
        inline operator size_t() const;
        inline void fieldRecurse(Board &board, size_t level);
        inline void operator delete(void*);
        inline ~Field();
    };
    
    class Tile : public Listing {
    };
    
    class Row : public Listing {
    };
    
    class Column : public Listing {
    };
    
    class Board {
        typedef std::aligned_storage<sizeof(Field), alignof(Field)>::type    FieldPod;
        FieldPod    fields[SIDE_4];
    
    public:
        inline Board();
        inline Field& operator [](size_t idx);
        inline ~Board();
    };
    
    std::ostream& operator <<(std::ostream &stream, const Field &field);
    static inline void recurse(Board &board, size_t level);
    
    inline
    Listing::operator Assignment *() {
        return static_cast<Assignment *>(this);
    }
    
    inline
    Listing::Listing() :
        fieldPrev(static_cast<Assignment *>(this)),
        fieldNext(static_cast<Assignment *>(this)),
        tilePrev(static_cast<Assignment *>(this)),
        tileNext(static_cast<Assignment *>(this)),
        rowPrev(static_cast<Assignment *>(this)),
        rowNext(static_cast<Assignment *>(this)),
        columnPrev(static_cast<Assignment *>(this)),
        columnNext(static_cast<Assignment *>(this))
    {}
    
    inline
    Listing::Listing(Field &field, Tile &tile, Row &row, Column &column) :
        fieldPrev(field.fieldPrev),
        fieldNext(static_cast<Assignment *>(static_cast<Listing *>(&field))),
        tilePrev(tile.tilePrev),
        tileNext(static_cast<Assignment *>(static_cast<Listing *>(&tile))),
        rowPrev(row.rowPrev),
        rowNext(static_cast<Assignment *>(static_cast<Listing *>(&row))),
        columnPrev(column.columnPrev),
        columnNext(static_cast<Assignment *>(static_cast<Listing *>(&column)))
    {
        field.fieldPrev = static_cast<Assignment *>(this);
        fieldPrev->fieldNext = static_cast<Assignment *>(this);
        tile.tilePrev = static_cast<Assignment *>(this);
        tilePrev->tileNext = static_cast<Assignment *>(this);
        row.rowPrev = static_cast<Assignment *>(this);
        rowPrev->rowNext = static_cast<Assignment *>(this);
        column.columnPrev = static_cast<Assignment *>(this);
        columnPrev->columnNext = static_cast<Assignment *>(this);
    }
    
    inline Assignment*
    Listing::prev() const {
        return fieldPrev;
    }
    
    inline Assignment*
    Listing::next() const {
        return fieldNext;
    }
    
    inline void
    Listing::discard() {
        fieldPrev = *this;
        fieldNext = *this;
    }
    
    inline
    Listing::~Listing() {
        fieldPrev->fieldNext = fieldNext;
        fieldNext->fieldPrev = fieldPrev;
        tilePrev->tileNext = tileNext;
        tileNext->tilePrev = tilePrev;
        rowPrev->rowNext = rowNext;
        rowNext->rowPrev = rowPrev;
        columnPrev->columnNext = columnNext;
        columnNext->columnPrev = columnPrev;
    }
    
    inline
    Assignment::Assignment(Field &field, Tile &tile, Row &row, Column &column, size_t value_) :
        Listing(field, tile, row, column),
        value(value_)
    {}
    
    inline
    Assignment::operator size_t() const {
        return value;
    }
    
    inline void
    Assignment::fieldHide(Assignment **order) {
        if (*this == fieldNext->fieldPrev) {
            fieldPrev->fieldNext = fieldNext;
            fieldNext->fieldPrev = fieldPrev;
            hidingOrder = *order;
            *order = this;
        }
    }
    
    inline void
    Assignment::hide(Assignment **order) {
        for (Assignment *as = tileNext; *this != as; as = as->tileNext) as->fieldHide(order);
        for (Assignment *as = rowNext; *this != as; as = as->rowNext) as->fieldHide(order);
        for (Assignment *as = columnNext; *this != as; as = as->columnNext) as->fieldHide(order);
        fieldPrev->fieldNext = fieldNext;
        fieldNext->fieldPrev = fieldPrev;
        hidingOrder = *order;
        *order = this;
    }
    
    inline void
    Assignment::fieldShow() {
        fieldNext->fieldPrev = *this;
        fieldPrev->fieldNext = *this;
    }
    
    inline void
    Assignment::show(Assignment *order) {
        while (order) {
            order->fieldShow();
            order = order->hidingOrder;
        }
    }
    
    inline
    Field::Field(Tile (&tile)[SIDE_2], Row (&row)[SIDE_2], Column (&column)[SIDE_2]) {
        for (size_t value = 0; value < SIDE_2; ++value)
            new Assignment(*this, tile[value], row[value], column[value], value + 1);
    }
    
    inline
    Field::operator size_t() const {
        return value;
    }
    
    inline void
    Field::fieldRecurse(Board &board, size_t level) {
        Assignment    *hiding = nullptr;
    
        for (Assignment *as = next(); *this != as; as = as->next()) {
            as->hide(&hiding);
            value = *as;
            recurse(board, level + 1);
            as->show(hiding);
        }
    }
    
    inline void
    Field::operator delete(void*) {
    }
    
    inline
    Field::~Field() {
        Assignment    *las = prev();
        if (*this != las) {
            for (Assignment    *as = las->prev(); *this != as; as = as->prev()) {
                delete las;
                las = as;
            }
            delete las;
        }
        discard();
    }
    
    inline
    Board::Board() {
        Tile (*const tiles)[SIDE][SIDE_2] = new Tile[SIDE][SIDE][SIDE_2];
        Row (*const rows)[SIDE_2] = new Row[SIDE_2][SIDE_2];
        Column (*const columns)[SIDE_2] = new Column[SIDE_2][SIDE_2];
        
        for (size_t row = 0; row < SIDE_2; ++row) {
            for (size_t column = 0; column < SIDE_2; ++column) {
                new (&fields[row * SIDE_2 + column])
                Field(
                    tiles[row / SIDE][column / SIDE],
                    rows[row],
                    columns[column]
                );
            }
        }
    
        delete[] columns;
        delete[] rows;
        delete[] tiles;
    }
    
    inline Field&
    Board::operator [](size_t idx) {
        return *reinterpret_cast<Field *>(&fields[idx]);
    }
    
    inline
    Board::~Board() {
        for (size_t field = 0; field < SIDE_4; ++field) {
            delete reinterpret_cast<Field *>(&fields[field]);
        }
    }
    
    std::ostream&
    operator <<(std::ostream &stream, const Field &field) {
        stream << (size_t) field;
    
        return stream;
    }
    
    static inline void
    recurse(Board &board, size_t level) {
        if (SIDE_4 == level) {
            for (size_t row = 0; row < SIDE_2; ++row) {
                std::cout
                    << std::setw(FILL - 1) << std::setfill(' ')
                    << board[row * SIDE_2];
                for (size_t column = 1; column < SIDE_2; ++column)
                    std::cout
                        << std::setw(FILL) << std::setfill(' ')
                        << board[row * SIDE_2 + column];
                std::cout << std::endl;
            }
            std::cout << std::endl;
        } else {
            board[level].fieldRecurse(board, level);
        }
    }
    
    int
    main() {
        Board    *board = new Board();
    
        recurse(*board, 0);
        delete board;
        return (0);
    }
    

    Založit nové vláknoNahoru

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.