/* Generating HTML pages for CWP Copyright (C) 2016 Frans Faase This program is used to generate HTML pages for the Chinese Wooden Puzzles on my website. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. GNU General Public License: http://www.iwriteiam.nl/GNU.txt Details: http://www.iwriteiam.nl/D1602.html#7 */ #include #include #include #include #define ASSERT(C,T) assert(C,T);//if (!(C)) { printf(T "\n"); exit(1); } void assert(bool test, const char *s) { if (!(test)) { printf("%s\n", s); exit(1); } } #define MAX_PLURALITY 5 #define MAX_PIECES 8 class UndoContext; class Undoable { friend class UndoContext; public: Undoable() : _in(false) {} void addToUndoContext() { ASSERT(!_in, "Double removed") _prev_undoable = _undoable; _in = true; _undoable = this; } virtual void undo() = 0; private: static void undo_till(Undoable *till) { while (_undoable != till) { _undoable->undo(); _undoable->_in = false; _undoable = _undoable->_prev_undoable; } } static Undoable* _undoable; Undoable *_prev_undoable; bool _in; }; Undoable *Undoable::_undoable = 0; class UndoContext { public: UndoContext() : _till(Undoable::_undoable) {} ~UndoContext() { Undoable::undo_till(_till); } private: Undoable* _till; }; template class Chain : public Undoable { public: Chain(T* n_owner = 0, S* n_parent = 0) : next(this), prev(this), owner(n_owner), parent(n_parent) {} bool isEmpty() { return next == this; } void push_back(Chain* chain) { chain->prev = prev; prev->next = chain; prev = chain; chain->next = this; } bool empty() { return next == this; } int size() { int result = 0; for (Chain* it = next; it != this; it = it->next) result++; return result; } void remove() { next->prev = prev; prev->next = next; Undoable::addToUndoContext(); } virtual void undo() { next->prev = this; prev->next = this; } class Iterator { public: Iterator(Chain& chain) { _end = &chain; _cur = chain.next; } Iterator(Iterator& it) { _end = it._end; _cur = it._cur; } bool more() { return _cur != _end; } void next() { _cur = _cur->next; } T* owner() { return _cur->owner; } S* parent() { return _cur->parent; } private: Chain* _end; Chain* _cur; }; Chain* next; Chain* prev; T* owner; S* parent; }; template class Neighbour { public: typedef Chain,T> NChain; Neighbour(T* e1, NChain& c1, T* e2, NChain& c2) : chain1(this, e1), chain2(this, e2) { c1.push_back(&chain1); c2.push_back(&chain2); } void remove(NChain* c) { if (&chain1 == c) chain2.remove(); else chain1.remove(); } class Iterator { public: Iterator(NChain& chain) { _end = &chain; _cur = chain.next; } Iterator(Iterator& it) { _end = it._end; _cur = it._cur; } bool more() { return _cur != _end; } void next() { _cur = _cur->next; } T* value() { Neighbour* neighbour = _cur->owner; return &neighbour->chain1 == _cur ? neighbour->chain2.parent : neighbour->chain1.parent; } Neighbour* cur() { return _cur->owner; } void remove() { _cur->owner->remove(_cur); } private: NChain* _end; NChain* _cur; }; NChain chain1; NChain chain2; virtual void dummy() {} }; class PiecePlacement; class PiecePlacementNeighbour : public Neighbour { public: PiecePlacementNeighbour(PiecePlacement* e1, NChain& c1, PiecePlacement* e2, NChain& c2, int touching_val) : Neighbour(e1, c1, e2, c2), touching(touching_val) {} int touching; }; typedef PiecePlacementNeighbour::NChain PPNChain; class Cell; class PiecePlacementUseCell; typedef Chain CAPPChain; typedef Chain PPUCChainBase; class PPUCChain : public PPUCChainBase { public: PPUCChain(PiecePlacementUseCell* owner = 0, Cell* parent = 0) : PPUCChainBase(owner, parent) {} void push_back(PPUCChain* chain); void remove(); virtual void undo(); }; class PiecePlacementUseCell { public: PiecePlacementUseCell(PiecePlacement* pp, Cell* cell) : pp_chain(this, cell), c_chain(this, pp) {} class CellsIterator { public: CellsIterator(CAPPChain& chain) { _end = &chain; _cur = chain.next; } bool more() { return _cur != _end; } void next() { _cur = _cur->next; } Cell* cell() { return _cur->owner->pp_chain.parent; } void remove() { _cur->owner->pp_chain.remove(); } private: CAPPChain* _end; CAPPChain* _cur; }; class PiecePlacementIterator { public: PiecePlacementIterator(PPUCChain& chain) { _end = &chain; _cur = chain.next; } bool more() { return _cur != _end; } void next() { _cur = _cur->next; } PiecePlacement* piecePlacement() { return _cur->owner->c_chain.parent; } void remove() { _cur->owner->c_chain.remove(); } private: PPUCChainBase* _end; PPUCChainBase* _cur; }; PPUCChain pp_chain; CAPPChain c_chain; }; typedef Neighbour CellNeighbour; typedef Chain CellChain; class Cell { public: Cell() : nr_piece_placements(0), chain(this), accepted_placement(0) {} int nr; PPUCChain piece_placements; int nr_piece_placements; CellNeighbour::NChain neighbours; PiecePlacement* accepted_placement; int covered_by_placement; CellChain chain; }; void PPUCChain::push_back(PPUCChain* chain) { PPUCChainBase::push_back(chain); chain->parent->nr_piece_placements++; } void PPUCChain::remove() { PPUCChainBase::remove(); parent->nr_piece_placements--; } void PPUCChain::undo() { PPUCChainBase::undo(); parent->nr_piece_placements++; } class Piece; typedef Chain PieceChain; typedef Chain PPChain; int plurality = 5; class Piece { public: Piece() : chain(this), nr_sel_placements(0) { index = _nr_pieces++; } PiecePlacement* newPlacement(); char name; int index; PPChain placements; bool all_selected() { return nr_sel_placements == plurality; } void add_selected(PiecePlacement* placement) { sel_placements[nr_sel_placements++] = placement; } void remove_selected(PiecePlacement* placement) { nr_sel_placements--; } int nr_sel_placements; PiecePlacement* sel_placements[MAX_PLURALITY]; void remove(); PieceChain chain; int nr_forced_placements; static int nr() { return _nr_pieces; } private: static int _nr_pieces; }; int Piece::_nr_pieces = 0; class PiecePlacement : Undoable { public: PiecePlacement(Piece* piece) : chain(this, piece), accepted(false), removed(false), possible(false), possible_at(0) {} void addCell(Cell *cell) { PiecePlacementUseCell* ppuc = new PiecePlacementUseCell(this, cell); cells.push_back(&ppuc->c_chain); cell->piece_placements.push_back(&ppuc->pp_chain); } void remove(Cell *cell = 0) { ASSERT(!removed, "PP already removed") ASSERT(!accepted, "PP remove accepted") removed = true; addToUndoContext(); // For neighbours for (PiecePlacementNeighbour::Iterator ppn_it(neighbours); ppn_it.more(); ppn_it.next()) ppn_it.remove(); // For cells for (PiecePlacementUseCell::CellsIterator cell_it(cells); cell_it.more(); cell_it.next()) if (cell_it.cell() != cell) cell_it.remove(); chain.remove(); // -- for resetting removed flag } void accept() { ASSERT(!removed, "PP already removed") ASSERT(!accepted, "PP already accepted") addToUndoContext(); // For cells covered by this placement for (PiecePlacementUseCell::CellsIterator cell_it(cells); cell_it.more(); cell_it.next()) { Cell* cell = cell_it.cell(); cell->accepted_placement = this; // Remove the cell from still available cells cell->chain.remove(); // Remove all piece placements that have this cell, except ourselved of course for (PiecePlacementUseCell::PiecePlacementIterator pp_it(cell->piece_placements); pp_it.more(); pp_it.next()) { PiecePlacement* overlapping_pp = pp_it.piecePlacement(); if (overlapping_pp != this) overlapping_pp->remove(cell); } } chain.parent->add_selected(this); if (chain.parent->all_selected()) { chain.parent->remove(); } accepted = true; } virtual void undo() { if (accepted) { chain.parent->remove_selected(this); // For cells covered by this placement for (PiecePlacementUseCell::CellsIterator cell_it(cells); cell_it.more(); cell_it.next()) { Cell* cell = cell_it.cell(); cell->accepted_placement = 0; } accepted = false; } if (removed) removed = false; } int nr; int dist; int dists[MAX_PLURALITY]; int extra_touching; PPNChain neighbours; CAPPChain cells; PPChain chain; bool accepted; bool removed; bool possible; int possible_at; }; PiecePlacement* Piece::newPlacement() { PiecePlacement* result = new PiecePlacement(this); placements.push_back(&result->chain); return result; } void Piece::remove() { for (PPChain::Iterator placement_it(placements); placement_it.more(); placement_it.next()) { for (PiecePlacementUseCell::CellsIterator cell_it(placement_it.owner()->cells); cell_it.more(); cell_it.next()) cell_it.remove(); } chain.remove(); } class PiecePlacements { public: PiecePlacements() : _elems(0), _size(0) {} ~PiecePlacements() { delete _elems; } bool empty() const { return _elems == 0; } int size() const { return _size; } void add(PiecePlacement* placement) { _elems = new Element(placement, _elems); _size++; } void add(PiecePlacement* placement, int extra_touching) { Element** ref = &_elems; while (*ref != 0 && (*ref)->extra_touching < extra_touching) ref = &(*ref)->next; *ref = new Element(placement, extra_touching, *ref); _size++; } void remove(PiecePlacement* placement) { for (Element** ref = &_elems; *ref != 0; ref = &(*ref)->next) if ((*ref)->value == placement) { Element* old = *ref; *ref = old->next; old->next = 0; delete old; _size--; return; } } private: struct Element { Element(PiecePlacement* v, Element* n) : value(v), extra_touching(0), next(n) {} Element(PiecePlacement* v, int et, Element* n) : value(v), extra_touching(et), next(n) {} ~Element() { delete next; } PiecePlacement* value; int extra_touching; Element* next; void* operator new(size_t size) { if (_alloc_elements != 0) { void *result = _alloc_elements; _alloc_elements = _alloc_elements->next; return result; } else return malloc(size); } void operator delete(void* p) { Element* elem = (Element*)p; elem->next = _alloc_elements; _alloc_elements = elem; } private: static Element* _alloc_elements; }; public: class Iterator { public: Iterator(PiecePlacements &piecePlacements) : _it(piecePlacements._elems) {} bool more() { return _it != 0; } void next() { _it = _it->next; } PiecePlacement* value() { return _it->value; } int extra_touching() { return _it->extra_touching; } private: Element* _it; }; friend class PiecePlacements::Iterator; private: Element* _elems; int _size; }; PiecePlacements::Element* PiecePlacements::Element::_alloc_elements = 0; void makeNeighbours(PiecePlacement* pp1, PiecePlacement* pp2, int touching) { new PiecePlacementNeighbour(pp1, pp1->neighbours, pp2, pp2->neighbours, touching); } Cell *cells; CellChain all_cells; PieceChain all_pieces; void read_puzzle(FILE *fin) { int nr_cells; int nr_pieces; fscanf(fin, "%d %d", &nr_cells, &nr_pieces); cells = new Cell[nr_cells]; for (int i = 0; i < nr_cells; i++) { cells[i].nr = i; all_cells.push_back(&cells[i].chain); } Piece *pieces = new Piece[nr_pieces]; for (int i = 0; i < nr_pieces; i++) { pieces[i].name = 'a' + i; all_pieces.push_back(&pieces[i].chain); } for (int p = 0; p < nr_pieces; p++) { int nr_placements; fscanf(fin, "%d", &nr_placements); Piece* piece = &pieces[p]; for (int o_p = 0; o_p < nr_placements; o_p++) { PiecePlacement* placement = piece->newPlacement(); placement->nr = o_p; int nr_pp_cells; fscanf(fin, "%d", &nr_pp_cells); for (int l = 0; l < nr_pp_cells; l++) { int lnr; fscanf(fin, "%d", &lnr); if (lnr < 0 || lnr >= nr_cells) { fprintf(stderr, "Error: Piece %d, orientation %d, found %d\n", p, o_p, lnr); return; } placement->addCell(&cells[lnr]); } } } int nr_neighbours = 0; fscanf(fin, "%d", &nr_neighbours); if (nr_neighbours == 0) { printf("Error: Neighbour definition missing. (Run gen_dpfp with -n option)\n"); exit(1); } for (int n = 0; n < nr_neighbours; n++) { int i,j; fscanf(fin, "%d %d", &i, &j); Cell* cell1 = &cells[i]; Cell* cell2 = &cells[j]; new CellNeighbour(cell1, cell1->neighbours, cell2, cell2->neighbours); } } void find_neighbours() { for (PieceChain::Iterator piece(all_pieces); piece.more(); piece.next()) { int nr = 0; PPChain &placements = piece.owner()->placements; for (PPChain::Iterator placement1(placements); placement1.more(); placement1.next()) { PPChain::Iterator placement2(placement1); for (placement2.next(); placement2.more(); placement2.next()) { bool overlap = false; int touching = 0; for (CAPPChain::Iterator capp1(placement1.owner()->cells); capp1.more(); capp1.next()) { Cell *cell1 = capp1.owner()->pp_chain.parent; for (CAPPChain::Iterator capp2(placement2.owner()->cells); capp2.more(); capp2.next()) { Cell *cell2 = capp2.owner()->pp_chain.parent; if (cell1 == cell2) overlap = true; if (!overlap) { for (CellNeighbour::Iterator neighbour(cell1->neighbours); neighbour.more(); neighbour.next()) if (neighbour.value() == cell2) { touching++; break; } } } } if (!overlap && touching > 0) { nr++; makeNeighbours(placement1.owner(), placement2.owner(), touching); } } } } } void print_state(FILE* f) { for (PieceChain::Iterator piece(all_pieces); piece.more(); piece.next()) { fprintf(f, "Piece %p %p\n", piece.owner(), piece.parent()); for (PPChain::Iterator placement(piece.owner()->placements); placement.more(); placement.next()) { fprintf(f, " placement(%d): ", placement.owner()->nr); for (CAPPChain::Iterator cell(placement.owner()->cells); cell.more(); cell.next()) { fprintf(f, " %d", cell.owner()->pp_chain.parent->nr); } for (PiecePlacementNeighbour::Iterator neighbour(placement.owner()->neighbours); neighbour.more(); neighbour.next()) { fprintf(f, " (%d)", neighbour.value()->nr); } fprintf(f, "\n"); } } for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next()) { fprintf(f, "Cell %d: %d\n", cell_it.owner()->nr, cell_it.owner()->nr_piece_placements); } } int max_extra_touching; int sq_n; int sq_m; #define CELL(X,Y) cells[(X)*sq_m + (Y)] long count; void process_solution(FILE* f, int extra_touching) { fprintf(f, "p(\""); for (int i = 0; i < sq_n; i++) { for (int j = 0; j < sq_m; j++) fprintf(f, "%c", CELL(i,j).accepted_placement->chain.parent->name); } fprintf(f, "\") // %d\n", extra_touching); fflush(f); count++; } bool neighbours(PiecePlacement* a, PiecePlacement* b) { for (PiecePlacementNeighbour::Iterator placement_it(a->neighbours); placement_it.more(); placement_it.next()) if (placement_it.value() == b) return true; return false; } int neighboursTouching(PiecePlacement* a, PiecePlacement* b) { for (PiecePlacementNeighbour::Iterator placement_it(a->neighbours); placement_it.more(); placement_it.next()) if (placement_it.value() == b) return dynamic_cast(placement_it.cur())->touching; return 0; } void print(PiecePlacement* placement) { int i = 0; for (CAPPChain::Iterator cell_it(placement->cells); cell_it.more(); cell_it.next()) { printf("%c%d", i == 0 ? ' ' : ',', cell_it.owner()->pp_chain.parent->nr); i++; } } bool exclude_cycle = false; bool exclude_tree = false; void remove_impossible() { bool go = true; while (go) { go = false; for (PieceChain::Iterator piece_it(all_pieces); piece_it.more(); piece_it.next()) { Piece* piece = piece_it.owner(); for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next()) { if (!placement_it.owner()->accepted) { bool zero_placements = false; bool one_placement = false; { UndoContext acceptContext; placement_it.owner()->accept(); for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next()) if (cell_it.owner()->nr_piece_placements == 0) { zero_placements = true; break; } else if (cell_it.owner()->nr_piece_placements == 1) one_placement = true; } if (zero_placements) { placement_it.owner()->remove(); go = true; } } } } } } void solve_by_grid(Piece* last_piece, int extra_touching) { if (extra_touching > max_extra_touching) return; UndoContext removedPiecePlacementsContext; // First remove all pieces placements which cannot be placed, because they would make // it impossible for some cells to be covered. // This is an iterative process, because if a placement is impossible, this could // make other placements impossible as well. PiecePlacements poss_piece_placement_per_piece[MAX_PIECES]; int min_extra_per_piece[MAX_PIECES]; int total_min_extra = 0; for (PieceChain::Iterator piece_it(all_pieces); piece_it.more(); piece_it.next()) { Piece* piece = piece_it.owner(); int nr_sel_placements = piece->nr_sel_placements; if (nr_sel_placements > 0) { // Determine number of groups of connected piece placements for this piece int groups[MAX_PLURALITY]; for (int i = 0; i < nr_sel_placements; i++) groups[i] = i; for (int j = 1; j < nr_sel_placements; j++) for (int i = 0; i < j; i++) if (groups[i] != groups[j] && neighboursTouching(piece->sel_placements[i], piece->sel_placements[j]) > 0) { int groupsi = groups[i]; int groupsj = groups[j]; if (groupsj < groupsi) { int t = groupsj; groupsj = groupsi; groupsi = t; } for (int k = 0; k < nr_sel_placements; k++) if (groups[k] == groupsj) groups[k] = groupsi; } // normalize int map[MAX_PLURALITY]; for (int i = 0; i < nr_sel_placements; i++) map[i] = -1; int nr_groups = 0; for (int i = 0; i < nr_sel_placements; i++) if (map[groups[i]] == -1) map[groups[i]] = nr_groups++; for (int i = 0; i < nr_sel_placements; i++) groups[i] = map[groups[i]]; int left = plurality - nr_sel_placements; // Initialize nrs for each group for (PPChain::Iterator placement_it(piece->placements); placement_it.more(); placement_it.next()) { PiecePlacement* piece_placement = placement_it.owner(); piece_placement->dist = 0; piece_placement->extra_touching = 0; for (int group = 0; group < nr_groups; group++) piece_placement->dists[group] = 0; } PiecePlacements& poss_piece_placements = poss_piece_placement_per_piece[piece->index]; // Process by group for (int group = 0; group < nr_groups; group++) { for (int i = 0; i < nr_sel_placements; i++) if (groups[i] == group) for (PiecePlacementNeighbour::Iterator placement_it(piece->sel_placements[i]->neighbours); placement_it.more(); placement_it.next()) { PiecePlacement* neighbour = placement_it.value(); if (!neighbour->accepted) { int touching = dynamic_cast(placement_it.cur())->touching; if (neighbour->dists[group] == 0) { neighbour->extra_touching += touching - 1; neighbour->dists[group] = 1; if (neighbour->dist == 0) { poss_piece_placements.add(neighbour); neighbour->dist = 1; } } else neighbour->extra_touching += touching; if (neighbour->extra_touching + extra_touching > max_extra_touching) { poss_piece_placements.remove(neighbour); neighbour->remove(); } } } for (int d = 1; d < left; d++) { int d_n = d + 1; for (PPChain::Iterator placement_it(piece->placements); placement_it.more(); placement_it.next()) { PiecePlacement* piece_placement = placement_it.owner(); if (piece_placement->dists[group] == d) for (PiecePlacementNeighbour::Iterator placement_it(piece_placement->neighbours); placement_it.more(); placement_it.next()) { PiecePlacement* neighbour = placement_it.value(); if (!neighbour->accepted && neighbour->dists[group] == 0) { neighbour->dists[group] = d_n; if (neighbour->dist == 0 || neighbour->dist > d_n) neighbour->dist = d_n; } } } } } if (poss_piece_placements.empty()) return; // -- found a piece without possible placements if (nr_groups > 1) { if (left == 1) { // Remove all placements that do not connect all groups for (PiecePlacements::Iterator placement_it(poss_piece_placements); placement_it.more();) { PiecePlacement* piece_placement = placement_it.value(); placement_it.next(); for (int group = 0; group < nr_groups; group++) if (piece_placement->dists[group] == 0) { poss_piece_placements.remove(piece_placement); piece_placement->remove(); break; } } if (poss_piece_placements.empty()) return; // -- found a piece without possible placements } else { // Check if groups can be connected int congroups[MAX_PLURALITY]; for (int i = 0; i < nr_groups; i++) congroups[i] = i; int uncon_groups = nr_groups; for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next()) { PiecePlacement* piece_placement = placement_it.owner(); if (piece_placement->dist != 0) { for (int j = 1; j < nr_groups; j++) for (int i = 0; i < j; i++) if ( congroups[i] != congroups[j] && piece_placement->dists[i] != 0 && piece_placement->dists[j] != 0 && piece_placement->dists[i] + piece_placement->dists[j] <= left+1) { uncon_groups--; int groupsi = congroups[i]; int groupsj = congroups[j]; if (groupsj < groupsi) { int t = groupsj; groupsj = groupsi; groupsi = t; } for (int k = 0; k <= nr_groups; k++) if (congroups[k] == groupsj) congroups[k] = groupsi; } if (uncon_groups == 1) break; } } if (uncon_groups > 1) return; // -- some groups cannot be connected } } // Remove unreachable piece placements for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next()) { PiecePlacement* piece_placement = placement_it.owner(); if (!piece_placement->accepted && piece_placement->dist == 0) piece_placement->remove(); } int min_extra_touching = 1000; for (PiecePlacements::Iterator placement_it(poss_piece_placements); placement_it.more(); placement_it.next()) { int extra_touching = placement_it.value()->extra_touching; if (extra_touching < min_extra_touching) { min_extra_touching = extra_touching; if (extra_touching == 0) break; } } min_extra_per_piece[piece->index] = min_extra_touching; total_min_extra += min_extra_touching; } } Piece* difficult_piece = 0; int difficult_piece_nr; for (PieceChain::Iterator piece_it(all_pieces); piece_it.more(); piece_it.next()) { Piece* piece = piece_it.owner(); int nr_sel_placements = piece->nr_sel_placements; if (nr_sel_placements > 0) { PiecePlacements& poss_piece_placements = poss_piece_placement_per_piece[piece->index]; if (total_min_extra > 0) { int others_extra = total_min_extra - min_extra_per_piece[piece->index]; if (others_extra > 0) { for (PiecePlacements::Iterator placement_it(poss_piece_placements); placement_it.more();) { PiecePlacement* placement = placement_it.value(); placement_it.next(); if (!placement->accepted && placement->extra_touching + extra_touching + others_extra > max_extra_touching) { poss_piece_placements.remove(placement); //placement->remove(); } } if (poss_piece_placements.empty()) return; } } if (difficult_piece == 0 || difficult_piece_nr > poss_piece_placements.size()) { difficult_piece = piece; difficult_piece_nr = poss_piece_placements.size(); } } } if (all_cells.empty()) { process_solution(stdout, extra_touching); return; } // Find the cell with the least number of placements left Cell* cell = 0; int min_nr_piece_placements = 0; for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next()) { if (cell == 0 || cell_it.owner()->nr_piece_placements < min_nr_piece_placements) { cell = cell_it.owner(); min_nr_piece_placements = cell->nr_piece_placements; if (min_nr_piece_placements == 0) return; } } PiecePlacements selected_piece_placements; if (difficult_piece != 0 && difficult_piece_nr < min_nr_piece_placements) { for (PiecePlacements::Iterator placement_it(poss_piece_placement_per_piece[difficult_piece->index]); placement_it.more(); placement_it.next()) { PiecePlacement* piece_placement = placement_it.value(); selected_piece_placements.add(piece_placement, piece_placement->extra_touching); } } else { for (PiecePlacementUseCell::PiecePlacementIterator piece_placement_it(cell->piece_placements); piece_placement_it.more(); piece_placement_it.next()) { PiecePlacement* piece_placement = piece_placement_it.piecePlacement(); Piece* piece = piece_placement->chain.parent; selected_piece_placements.add(piece_placement, piece->nr_sel_placements == 0 ? 0 : piece_placement->extra_touching); } } for (PiecePlacements::Iterator placement_it(selected_piece_placements); placement_it.more(); placement_it.next()) { PiecePlacement* piece_placement = placement_it.value(); if (!piece_placement->removed) { { UndoContext acceptPiecePlacement; piece_placement->accept(); solve_by_grid(piece_placement->chain.parent, extra_touching + placement_it.extra_touching()); } piece_placement->remove(); } } } void placePiece(int p1, int p2, int p3, int p4) { for (PieceChain::Iterator piece(all_pieces); piece.more(); piece.next()) { for (PPChain::Iterator placement(piece.owner()->placements); placement.more(); placement.next()) { bool found_p1 = false; bool found_p2 = false; bool found_p3 = false; bool found_p4 = false; for (CAPPChain::Iterator cell(placement.owner()->cells); cell.more(); cell.next()) { if (cell.owner()->pp_chain.parent->nr == p1) found_p1 = true; else if (cell.owner()->pp_chain.parent->nr == p2) found_p2 = true; else if (cell.owner()->pp_chain.parent->nr == p3) found_p3 = true; else if (cell.owner()->pp_chain.parent->nr == p4) found_p4 = true; } if (found_p1 && found_p2 && found_p3 && found_p4) { placement.owner()->accept(); return; } } } printf("Did not find %d,%d,%d,%d\n", p1, p2, p3, p4); } int main(int argc, char *argv[]) { if (argc != 5 || atoi(argv[1]) <= 0 || atoi(argv[2]) <= 0 || atoi(argv[3]) <= 0 || atoi(argv[4]) < 0) exit(-1); sq_n = atoi(argv[2]); sq_m = atoi(argv[1]); plurality = atoi(argv[3]); max_extra_touching = atoi(argv[4]); FILE* f = stdin; if (f == 0) { printf("File not found\n"); return 1; } read_puzzle(f); fclose(f); find_neighbours(); remove_impossible(); solve_by_grid(0, 0); return 0; }