File indexing completed on 2024-11-03 06:54:50
0001 /* 0002 SPDX-FileCopyrightText: 2004-2005 Andi Peredri <andi@ukr.net> 0003 SPDX-FileCopyrightText: 2007-2008 Fela Winkelmolen <fela.kde@gmail.com> 0004 0005 SPDX-License-Identifier: GPL-2.0-or-later 0006 */ 0007 0008 #include "abstractgrid.h" 0009 0010 #include <QMap> 0011 #include <QString> 0012 #include <QDebug> 0013 #include <QRandomGenerator> 0014 0015 AbstractCell::AbstractCell(int index) 0016 : m_index(index) 0017 { 0018 makeEmpty(); 0019 } 0020 0021 char *AbstractCell::toString() { 0022 char *str = new char[4]; 0023 str[0] = (m_cables & Left) ? '-' : ' ' ; 0024 str[2] = (m_cables & Right) ? '-' : ' ' ; 0025 if ((m_cables & Up) && (m_cables & Down)) { 0026 str[1] = '|'; 0027 } else if (m_cables & Up) { 0028 str[1] = '\''; 0029 } else if (m_cables & Down) { 0030 str[1] = ','; 0031 } else if ((m_cables & Left) && (m_cables & Right)){ 0032 str[1] = '-'; 0033 } else { 0034 str[1] = ' '; 0035 } 0036 str[3] = '\0'; 0037 0038 return str; 0039 } 0040 0041 bool AbstractCell::isTerminal() const 0042 { 0043 if (m_isServer){ 0044 return false; 0045 } 0046 return (m_cables == Up || m_cables == Right 0047 || m_cables == Down || m_cables == Left); 0048 } 0049 0050 // only used to change the cables (not to rotate the cell!) 0051 void AbstractCell::setCables(Directions newCables) 0052 { 0053 m_cables = originalCables = newCables; 0054 m_hasBeenMoved = false; 0055 } 0056 0057 void AbstractCell::setServer(bool isServer) 0058 { 0059 m_isServer = isServer; 0060 } 0061 0062 void AbstractCell::setConnected(bool isConnected) 0063 { 0064 m_isConnected = isConnected; 0065 } 0066 0067 void AbstractCell::makeEmpty() 0068 { 0069 m_cables = originalCables = None; 0070 m_isServer = false; 0071 m_isConnected = false; 0072 m_hasBeenMoved = false; 0073 } 0074 0075 void AbstractCell::emptyMove() 0076 { 0077 m_hasBeenMoved = true; 0078 } 0079 0080 void AbstractCell::rotateClockwise() 0081 { 0082 Directions newdirs = None; 0083 if (m_cables & Up) newdirs = Directions(newdirs | Right); 0084 if (m_cables & Right) newdirs = Directions(newdirs | Down); 0085 if (m_cables & Down) newdirs = Directions(newdirs | Left); 0086 if (m_cables & Left) newdirs = Directions(newdirs | Up); 0087 m_cables = newdirs; 0088 m_hasBeenMoved = true; 0089 } 0090 0091 void AbstractCell::rotateCounterclockwise() 0092 { 0093 Directions newdirs = None; 0094 if (m_cables & Up) newdirs = Directions(newdirs | Left); 0095 if (m_cables & Right) newdirs = Directions(newdirs | Up); 0096 if (m_cables & Down) newdirs = Directions(newdirs | Right); 0097 if (m_cables & Left) newdirs = Directions(newdirs | Down); 0098 m_cables = newdirs; 0099 m_hasBeenMoved = true; 0100 } 0101 0102 void AbstractCell::invert() 0103 { 0104 rotateClockwise(); 0105 rotateClockwise(); 0106 } 0107 0108 void AbstractCell::reset() 0109 { 0110 m_cables = originalCables; 0111 m_hasBeenMoved = false; 0112 } 0113 0114 0115 0116 AbstractGrid::AbstractGrid() 0117 : m_width(0), m_height(0) 0118 { 0119 } 0120 0121 AbstractGrid::~AbstractGrid() 0122 { 0123 qDeleteAll(m_cells); 0124 } 0125 0126 void AbstractGrid::initializeGrid(uint width, uint height, Wrapping wrapping) 0127 { 0128 if ((width * height) != (m_width * m_height)) { 0129 qDeleteAll(m_cells); 0130 m_cells.clear(); 0131 0132 for (uint index = 0; index < width*height; ++index) { 0133 m_cells.append(newCell(index)); 0134 } 0135 } 0136 0137 m_width = width; 0138 m_height = height; 0139 m_isWrapped = wrapping; 0140 0141 createGrid(); 0142 0143 while(hasUnneededCables() || solutionCount() != 1) { 0144 // the grid is invalid: create a new one 0145 createGrid(); 0146 } 0147 0148 m_minimumMoves = 0; 0149 const int shuffleLimit = cellCount() * minCellRatio; 0150 QList<int> notShuffledCells; 0151 for (int i = 0; i < cellCount(); ++i) 0152 notShuffledCells.append(i); 0153 0154 // select a random cell that is not yet shuffled 0155 // rotate such that initial and final states are not same 0156 // repeat above two steps until minimum moves equal to shuffle limit 0157 auto *generator = QRandomGenerator::global(); 0158 while(m_minimumMoves < shuffleLimit) 0159 { 0160 // selecting a random index 0161 int index = generator->bounded(notShuffledCells.count()); 0162 int cellNo = notShuffledCells[index]; 0163 // removing the selected index so that it must not be used again 0164 notShuffledCells.removeAt(index); 0165 AbstractCell *cell = m_cells[cellNo]; 0166 Directions dir = cell->cables(); 0167 0168 // excludes None(Empty cell) 0169 if (dir == None) { 0170 continue; 0171 } 0172 // if straight line rotate once 0173 // cant rotate twice(it will be back on its initial state) 0174 else if ((dir == (Up | Down)) || (dir == (Left | Right))) { 0175 m_minimumMoves += 1; 0176 cell->rotateClockwise(); 0177 } 0178 // for every other case rotate 1..3 times 0179 else { 0180 int rotation = generator->bounded(3) + 1; // 1..3 0181 // cant rotate twice when m_minimumMoves == shuffleLimit - 1 0182 if (m_minimumMoves == shuffleLimit - 1 && rotation == 2){ 0183 rotation = (generator->bounded(2))? 1 : 3; // 1 or 3 0184 } 0185 m_minimumMoves += (rotation == 3) ? 1 : rotation; 0186 while(rotation--) { 0187 cell->rotateClockwise(); 0188 } 0189 } 0190 } 0191 0192 updateConnections(); 0193 } 0194 0195 void AbstractGrid::print() { 0196 //system("clear"); 0197 QString str1; 0198 QString str2; 0199 int index = 0; 0200 for (uint r = 0; r < m_height; ++r) { 0201 for (uint c = 0; c < m_width; ++c) { 0202 str1 +=QLatin1String( m_cells[index]->toString() ); 0203 str1 += QLatin1String( " " ); 0204 if (m_cells[index]->hasBeenMoved()) { 0205 str2 += QLatin1String( "M " ); 0206 } else { 0207 str2 += QLatin1String( " " ); 0208 } 0209 ++index; 0210 } 0211 qDebug() << str1 << " " << str2; 0212 qDebug() << QLatin1String( " " ); 0213 str1 = str2 = QLatin1String( "" ); 0214 } 0215 } 0216 0217 // ============ auxiliary funciontions ===================== // 0218 0219 void AbstractGrid::createGrid() 0220 { 0221 // add a random server 0222 auto *generator = QRandomGenerator::global(); 0223 server_index = generator->bounded(cellCount()); 0224 0225 // number of cells that aren't free 0226 int notFreeCells = 0; 0227 const int minimumNumCells = cellCount() * minCellRatio; 0228 // retries until the minimum number of cells is big enough 0229 while (notFreeCells < minimumNumCells) { 0230 0231 for (int i = 0; i < cellCount(); ++i) { 0232 m_cells[i]->makeEmpty(); 0233 } 0234 m_cells[server_index]->setServer(true); 0235 0236 QList<uint> list; 0237 list.append(server_index); 0238 if (generator->bounded(2)) addRandomCable(list); 0239 0240 // add some random cables... 0241 // the list empties if there aren't many free cells left 0242 // (because of addRandomCable() not doing anything) 0243 while (!list.isEmpty()) { 0244 if (generator->bounded(2)) { 0245 addRandomCable(list); 0246 if (generator->bounded(2)) addRandomCable(list); 0247 list.erase(list.begin()); 0248 } 0249 else { 0250 list.append(list.first()); 0251 list.erase(list.begin()); 0252 } 0253 } 0254 0255 // count not empty cells 0256 notFreeCells = 0; 0257 for (int i = 0; i < cellCount(); ++i) { 0258 if (m_cells[i]->cables() != None) ++notFreeCells; 0259 } 0260 } 0261 } 0262 0263 // adds a random direction and moves on (if possible) 0264 void AbstractGrid::addRandomCable(QList<uint>& list) 0265 { 0266 int cell = list.first(); 0267 // find all the cells surrounding list.first() 0268 // (0 when cells don't exist) 0269 int ucell = uCell(cell); // up 0270 int rcell = rCell(cell); // right 0271 int dcell = dCell(cell); // down 0272 int lcell = lCell(cell); // left 0273 0274 QMap<Directions, int> freeCells; 0275 0276 // of those cells map the ones that are free 0277 if (ucell != NO_CELL && m_cells[ucell]->cables() == None) { 0278 freeCells[Up] = ucell; 0279 } 0280 if (rcell != NO_CELL && m_cells[rcell]->cables() == None) { 0281 freeCells[Right] = rcell; 0282 } 0283 if (dcell != NO_CELL && m_cells[dcell]->cables() == None) { 0284 freeCells[Down] = dcell; 0285 } 0286 if (lcell != NO_CELL && m_cells[lcell]->cables() == None) { 0287 freeCells[Left] = lcell; 0288 } 0289 0290 if (freeCells.isEmpty()) return; // no free cells left 0291 0292 QMap<Directions, int>::ConstIterator it = freeCells.constBegin(); 0293 // move the iterator to a random direction connecting to a free cell 0294 for (int i = QRandomGenerator::global()->bounded(freeCells.count()); i > 0; --i) ++it; 0295 0296 // add the cable in the direction of cell 0297 Directions newCables = Directions(m_cells[cell]->cables() | it.key()); 0298 m_cells[cell]->setCables(newCables); 0299 // add a cable in the opposite direction, on the free cell 0300 m_cells[it.value()]->setCables(invertDirection(it.key())); 0301 // append the cell that was free to the list 0302 list.append(it.value()); 0303 } 0304 0305 int AbstractGrid::uCell(uint cell) const 0306 { 0307 if (cell >= m_width) { 0308 return cell - m_width; 0309 } else if (m_isWrapped) { 0310 return m_width * (m_height - 1) + cell; 0311 } else { 0312 return NO_CELL; 0313 } 0314 } 0315 0316 int AbstractGrid::dCell(uint cell) const 0317 { 0318 if (cell < m_width * (m_height - 1)) { 0319 return cell + m_width; 0320 } else if (m_isWrapped) { 0321 return cell - m_width * (m_height - 1); 0322 } else { 0323 return NO_CELL; 0324 } 0325 } 0326 0327 int AbstractGrid::lCell(uint cell) const 0328 { 0329 if (cell % m_width > 0) { 0330 return cell - 1; 0331 } else if (m_isWrapped) { 0332 return cell - 1 + m_width; 0333 } else { 0334 return NO_CELL; 0335 } 0336 } 0337 0338 int AbstractGrid::rCell(uint cell) const 0339 { 0340 if (cell % m_width < m_width - 1) { 0341 return cell + 1; 0342 } else if (m_isWrapped) { 0343 return cell + 1 - m_width; 0344 } else { 0345 return NO_CELL; 0346 } 0347 } 0348 0349 // TODO: something better to invert directions (remove duplication etc...) 0350 Directions AbstractGrid::invertDirection(Directions givenDirection) 0351 { 0352 QMap<Directions, Directions> invDirs; 0353 invDirs[Up] = Down; 0354 invDirs[Right] = Left; 0355 invDirs[Down] = Up; 0356 invDirs[Left] = Right; 0357 0358 return invDirs[givenDirection]; 0359 } 0360 0361 0362 int AbstractGrid::solutionCount() 0363 { 0364 MoveList possibleNextMoves; 0365 // TODO: put following in external function 0366 for (AbstractCell *cell : std::as_const(m_cells)) { 0367 if (!cell->hasBeenMoved()) { 0368 Directions dirs = cell->cables(); 0369 Move move; 0370 if (dirs == None) { 0371 // no cables 0372 move = Move(cell->index(), Move::None); 0373 possibleNextMoves.append(move); 0374 } else if (dirs == (Up | Down) || dirs == (Left | Right)) { 0375 // cables forming a line 0376 move = Move(cell->index(), Move::None); 0377 possibleNextMoves.append(move); 0378 0379 move = Move(cell->index(), Move::Left); 0380 possibleNextMoves.append(move); 0381 } else { 0382 // other kind of cables 0383 move = Move(cell->index(), Move::None); 0384 possibleNextMoves.append(move); 0385 0386 move = Move(cell->index(), Move::Left); 0387 possibleNextMoves.append(move); 0388 0389 move = Move(cell->index(), Move::Right); 0390 possibleNextMoves.append(move); 0391 0392 move = Move(cell->index(), Move::Inverted); 0393 possibleNextMoves.append(move); 0394 } 0395 break; 0396 } 0397 } 0398 0399 // all cells have been moved 0400 if (possibleNextMoves.isEmpty()) { 0401 return isPossibleSolution() ? 1 : 0; 0402 } 0403 // else 0404 0405 int solutionsFound = 0; 0406 for (const Move &nextMove : std::as_const(possibleNextMoves)) { 0407 int index = nextMove.index(); 0408 0409 switch (nextMove.move()) { 0410 case Move::None: 0411 m_cells[index]->emptyMove(); 0412 break; 0413 case Move::Right: 0414 m_cells[index]->rotateClockwise(); 0415 break; 0416 case Move::Left: 0417 m_cells[index]->rotateCounterclockwise(); 0418 break; 0419 case Move::Inverted: 0420 m_cells[index]->invert(); 0421 break; 0422 } 0423 0424 if (movesDoneArePossible()) { 0425 solutionsFound += solutionCount(); // recursive call 0426 } 0427 0428 m_cells[index]->reset(); // undo move 0429 } 0430 return solutionsFound; 0431 } 0432 0433 bool AbstractGrid::movesDoneArePossible() 0434 { 0435 0436 for (AbstractCell *cell : std::as_const(m_cells)) { 0437 if (!cell->hasBeenMoved()) continue; 0438 0439 uint x = cell->index() % m_width; 0440 uint y = cell->index() / m_width; 0441 Directions cables = cell->cables(); 0442 0443 // check if there are moved cells near the borders that are wrong 0444 if (!m_isWrapped) { 0445 if (x == 0 && cables & Left) return false; 0446 if (x == m_width-1 && cables & Right) return false; 0447 if (y == 0 && cables & Up) return false; 0448 if (y == m_height-1 && cables & Down) return false; 0449 } 0450 0451 // check if there are contiguous moved cells that are wrong 0452 0453 if (cables & Left) { 0454 int lcell = lCell(cell->index()); 0455 if (lcell != NO_CELL && m_cells[lcell]->hasBeenMoved()) { 0456 // also the cell to the left of the current has been moved 0457 0458 // if it doesn't connect return false 0459 if (!(m_cells[lcell]->cables() & Right)) return false; 0460 } 0461 } 0462 if (cables & Right) { 0463 int rcell = rCell(cell->index()); 0464 if (rcell != NO_CELL && m_cells[rcell]->hasBeenMoved()) { 0465 if (!(m_cells[rcell]->cables() & Left)) return false; 0466 } 0467 } 0468 if (cables & Up) { 0469 int ucell = uCell(cell->index()); 0470 if (ucell != NO_CELL && m_cells[ucell]->hasBeenMoved()) { 0471 if (!(m_cells[ucell]->cables() & Down)) return false; 0472 } 0473 } 0474 if (cables & Down) { 0475 int dcell = dCell(cell->index()); 0476 if (dcell != NO_CELL && m_cells[dcell]->hasBeenMoved()) { 0477 if (!(m_cells[dcell]->cables() & Up)) return false; 0478 } 0479 } 0480 } 0481 0482 // nothing was wrong 0483 return true; 0484 } 0485 0486 bool AbstractGrid::hasUnneededCables() 0487 { 0488 for (AbstractCell *cell : std::as_const(m_cells)) { 0489 if (cell->isTerminal() || cell->isServer() || cell->cables() == None) { 0490 continue; 0491 } 0492 0493 Directions oldCables = cell->cables(); 0494 cell->setCables(None); 0495 0496 bool solution = isPossibleSolution(); 0497 cell->setCables(oldCables); 0498 0499 if (solution) { 0500 // it has a solution also when the cables of cell are removed 0501 return true; 0502 } 0503 } 0504 0505 return false; 0506 } 0507 0508 bool AbstractGrid::isPossibleSolution() 0509 { 0510 for (AbstractCell *cell : std::as_const(m_cells)) { 0511 cell->setConnected(false); 0512 } 0513 updateConnections(); 0514 0515 return allTerminalsConnected(); 0516 } 0517 0518 bool AbstractGrid::allTerminalsConnected() { 0519 // return false if there is a terminal that isn't connected 0520 for (AbstractCell *cell : std::as_const(m_cells)) { 0521 if (cell->isTerminal() && !cell->isConnected()) { 0522 return false; 0523 } 0524 } 0525 // all terminals are connected 0526 return true; 0527 } 0528 0529 QList<int> AbstractGrid::updateConnections() 0530 { 0531 // TODO: add int AbstractGrid::cellsCount() 0532 QList<bool> newConnections(m_width * m_height); 0533 for (uint i = 0; i < m_width * m_height; ++i) { 0534 newConnections[i] = false; 0535 } 0536 0537 // indexes of the changed cells 0538 QList<int> changedCells; 0539 changedCells.append(server_index); 0540 newConnections[server_index] = true; 0541 0542 while (!changedCells.isEmpty()) 0543 { 0544 int cell_index = changedCells.first(); 0545 int uindex = uCell(cell_index); 0546 int rindex = rCell(cell_index); 0547 int dindex = dCell(cell_index); 0548 int lindex = lCell(cell_index); 0549 0550 AbstractCell *cell = m_cells[cell_index]; 0551 AbstractCell *ucell = (uindex != NO_CELL) ? m_cells[uindex] : nullptr; 0552 AbstractCell *rcell = (rindex != NO_CELL) ? m_cells[rindex] : nullptr; 0553 AbstractCell *dcell = (dindex != NO_CELL) ? m_cells[dindex] : nullptr; 0554 AbstractCell *lcell = (lindex != NO_CELL) ? m_cells[lindex] : nullptr; 0555 0556 if ((cell->cables() & Up) && ucell != nullptr && 0557 (ucell->cables() & Down) && !newConnections[uindex]) { 0558 newConnections[uindex] = true; 0559 changedCells.append(ucell->index()); 0560 } 0561 if ((cell->cables() & Right) && rcell != nullptr && 0562 (rcell->cables() & Left) && !newConnections[rindex]) { 0563 newConnections[rindex] = true; 0564 changedCells.append(rcell->index()); 0565 } 0566 if ((cell->cables() & Down) && dcell != nullptr && 0567 (dcell->cables() & Up) && !newConnections[dindex]) { 0568 newConnections[dindex] = true; 0569 changedCells.append(dcell->index()); 0570 } 0571 if ((cell->cables() & Left) && lcell != nullptr && 0572 (lcell->cables() & Right) && !newConnections[lindex]) { 0573 newConnections[lindex] = true; 0574 changedCells.append(lcell->index()); 0575 } 0576 changedCells.erase(changedCells.begin()); 0577 } 0578 0579 // changedCells is empty here 0580 for (uint i = 0; i < m_width * m_height; i++){ 0581 AbstractCell *cell = m_cells[i]; 0582 if (cell->isConnected() != newConnections[i]) { 0583 changedCells.append(i); 0584 cell->setConnected(newConnections[i]); 0585 } 0586 } 0587 0588 return changedCells; 0589 } 0590