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í
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
dnes 16:00 | Nová verze

Byla vydána verze 0.98 svobodného nelineárního video editoru Pitivi. Z novinek lze zmínit například přizpůsobitelné klávesové zkratky. Videoukázka práce s nejnovější verzí Pitivi na YouTube.

Ladislav Hagara | Komentářů: 0
dnes 15:00 | Zajímavý software

Stop motion je technika animace, při níž je reálný objekt mezi jednotlivými snímky ručně upravován a posouván o malé úseky, tak aby po spojení vyvolala animace dojem spojitosti. Jaký software lze pro stop motion použít na Linuxu? Článek na OMG! Ubuntu! představuje Heron Animation. Ten bohužel podporuje pouze webové kamery. Podpora digitálních zrcadlovek je začleněna například v programu qStopMotion.

Ladislav Hagara | Komentářů: 1
včera 21:21 | Nová verze Ladislav Hagara | Komentářů: 0
včera 11:44 | Zajímavý projekt

Na Indiegogo byla spuštěna kampaň na podporu herní mini konzole a multimediálního centra RetroEngine Sigma od Doyodo. Předobjednat ji lze již od 49 dolarů. Požadovaná částka 20 000 dolarů byla překonána již 6 krát. Majitelé mini konzole si budou moci zahrát hry pro Atari VCS 2600, Sega Genesis nebo NES. Předinstalováno bude multimediální centrum Kodi.

Ladislav Hagara | Komentářů: 0
včera 00:10 | Nová verze

Byla vydána verze 4.7 redakčního systému WordPress. Kódové označením Vaughan bylo vybráno na počest americké jazzové zpěvačky Sarah "Sassy" Vaughan. Z novinek lze zmínit například novou výchozí šablonu Twenty Seventeen, náhledy pdf souborů nebo WordPress REST API.

Ladislav Hagara | Komentářů: 4
6.12. 12:00 | Zajímavý projekt

Projekt Termbox umožňuje vyzkoušet si linuxové distribuce Ubuntu, Debian, Fedora, CentOS a Arch Linux ve webovém prohlížeči. Řešení je postaveno na projektu HyperContainer. Podrobnosti v často kladených dotazech (FAQ). Zdrojové kódy jsou k dispozici na GitHubu [reddit].

Ladislav Hagara | Komentářů: 27
6.12. 11:00 | Bezpečnostní upozornění

Byly zveřejněny informace o bezpečnostní chybě CVE-2016-8655 v Linuxu zneužitelné k lokální eskalaci práv. Chyba se dostala do linuxového jádra v srpnu 2011. V upstreamu byla opravena minulý týden [Hacker News].

Ladislav Hagara | Komentářů: 2
5.12. 22:00 | Komunita

Přibližně před měsícem bylo oznámeno, že linuxová distribuce SUSE Linux Enterprise Server (SLES) běží nově také Raspberry Pi 3 (dokumentace). Obraz verze 12 SP2 pro Raspberry Pi 3 je ke stažení zdarma. Pro registrované jsou po dobu jednoho roku zdarma také aktualizace. Dnes bylo oznámeno, že pro Raspberry Pi 3 je k dispozici také nové openSUSE Leap 42.2 (zprávička). K dispozici je hned několik obrazů.

Ladislav Hagara | Komentářů: 6
5.12. 06:00 | Zajímavý software

OMG! Ubuntu! představuje emulátor terminálu Hyper (GitHub) postavený na webových technologiích (HTML, CSS a JavaScript). V diskusi k článku je zmíněn podobný emulátor terminálu Black Screen. Hyper i Black Screen používají framework Electron, stejně jako editor Atom nebo vývojové prostředí Visual Studio Code.

Ladislav Hagara | Komentářů: 50
5.12. 06:00 | Zajímavý článek

I letos vychází řada ajťáckých adventních kalendářů. QEMU Advent Calendar 2016 přináší každý den nový obraz disku pro QEMU. Programátoři se mohou potrápit při řešení úloh z kalendáře Advent of Code 2016. Kalendáře Perl Advent Calendar 2016 a Perl 6 Advent Calendar přinášejí každý den zajímavé informace o programovacím jazyce Perl. Stranou nezůstává ani programovací jazyk Go.

Ladislav Hagara | Komentářů: 10
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (23%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 792 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: Sudoku backtraking

16.2.2014 16:02 Oxydentist
Sudoku backtraking
Přečteno: 333×
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: 5 | 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: 43 | blog: Republic of Mordor | Zürich
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.