Administrace komentářů

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