knetwalk/src/abstractgrid.cpp

   1 /*
   2     Copyright 2004-2005 Andi Peredri <andi@ukr.net>
   3     Copyright 2007-2008 Fela Winkelmolen <fela.kde@gmail.com>
   4
   5     This program is free software: you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation, either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 #include "abstractgrid.h"
  20
  21 #include <cstdlib> // rand()
  22 #include <unistd.h> // sleep()
  23 #include <QMap>
  24 #include <QString>
  25 #include <KDebug>
  26
  27
  28 AbstractCell::AbstractCell(int index)
  29     : m_index(index)
  30 {
  31     makeEmpty();
  32 }
  33
  34 char *AbstractCell::toString() {
  35     char *str = new char[4];
  36     str[0] = (m_cables & Left) ? '-' : ' ';
  37     str[2] = (m_cables & Right) ? '-' : ' ';
  38     if ((m_cables & Up) && (m_cables & Down)) {
  39         str[1] = '|';
  40     } else if (m_cables & Up) {
  41         str[1] = '\'';
  42     } else if (m_cables & Down) {
  43         str[1] = ',';
  44     } else if ((m_cables & Left) && (m_cables & Right)){
  45         str[1] = '-';
  46     } else {
  47         str[1] = ' ';
  48     }
  49     str[3] = '\0';
  50
  51     return str;
  52 }
  53
  54 bool AbstractCell::isTerminal() const
  55 {
  56     return (m_cables == Up || m_cables == Right
  57             || m_cables == Down || m_cables == Left);
  58 }
  59
  60 // only used to change the cables (not to rotate the cell!)
  61 void AbstractCell::setCables(Directions newCables)
  62 {
  63     m_cables = originalCables = newCables;
  64     m_hasBeenMoved = false;
  65 }
  66
  67 void AbstractCell::setServer(bool isServer)
  68 {
  69     m_isServer = isServer;
  70 }
  71
  72 void AbstractCell::setConnected(bool isConnected)
  73 {
  74     m_isConnected = isConnected;
  75 }
  76
  77 void AbstractCell::makeEmpty()
  78 {
  79     m_cables = originalCables = None;
  80     m_isServer = false;
  81     m_isConnected = false;
  82     m_hasBeenMoved = false;
  83 }
  84
  85 void AbstractCell::emptyMove()
  86 {
  87     m_hasBeenMoved = true;
  88 }
  89
  90 void AbstractCell::turnClockwise()
  91 {
  92     Directions newdirs = None;
  93     if (m_cables & Up) newdirs = Directions(newdirs | Right);
  94     if (m_cables & Right) newdirs = Directions(newdirs | Down);
  95     if (m_cables & Down) newdirs = Directions(newdirs | Left);
  96     if (m_cables & Left) newdirs = Directions(newdirs | Up);
  97     m_cables = newdirs;
  98     m_hasBeenMoved = true;
  99 }
 100
 101 void AbstractCell::turnCounterclockwise()
 102 {
 103     Directions newdirs = None;
 104     if (m_cables & Up) newdirs = Directions(newdirs | Left);
 105     if (m_cables & Right) newdirs = Directions(newdirs | Up);
 106     if (m_cables & Down) newdirs = Directions(newdirs | Right);
 107     if (m_cables & Left) newdirs = Directions(newdirs | Down);
 108     m_cables = newdirs;
 109     m_hasBeenMoved = true;
 110 }
 111
 112 void AbstractCell::invert()
 113 {
 114     turnClockwise();
 115     turnClockwise();
 116 }
 117
 118 void AbstractCell::reset()
 119 {
 120     m_cables = originalCables;
 121     m_hasBeenMoved = false;
 122 }
 123
 124
 125
 126
 127
 128 AbstractGrid::~AbstractGrid()
 129 {
 130     while (!m_cells.isEmpty()) delete m_cells.takeFirst();
 131 }
 132
 133 void AbstractGrid::initializeGrid(uint width, uint height, Wrapping wrapping)
 134 {
 135     if ((width * height) != (m_width * m_height)) {
 136         while (!m_cells.isEmpty()) delete m_cells.takeFirst();
 137
 138         for (uint index = 0; index < width*height; ++index) {
 139             m_cells.append(newCell(index));
 140         }
 141     }
 142
 143     m_width = width;
 144     m_height = height;
 145     m_isWrapped = wrapping;
 146
 147     createGrid();
 148
 149     while(hasUnneededCables() || solutionCount() != 1) {
 150         // the grid is invalid: create a new one
 151         createGrid();
 152     }
 153
 154     // shuffle all cells
 155     for (uint i = 0; i < width*height; ++i) {
 156         int rotation = rand() % 4; // 0..3
 157         for (int j = 0; j < rotation; ++j) {
 158             // ratate every cable clockwise
 159             m_cells[i]->turnClockwise();
 160         }
 161     }
 162 }
 163
 164 void AbstractGrid::print() {
 165     system("clear");
 166     QString str1;
 167     QString str2;
 168     int index = 0;
 169     for (uint r = 0; r < m_height; ++r) {
 170         for (uint c = 0; c < m_width; ++c) {
 171             str1 += m_cells[index]->toString();
 172             str1 += "  ";
 173             if (m_cells[index]->hasBeenMoved()) {
 174                 str2 += "M ";
 175             } else {
 176                 str2 += "  ";
 177             }
 178             ++index;
 179         }
 180         kDebug() << str1 << "     " << str2;
 181         kDebug() << " ";
 182         str1 = str2 = "";
 183     }
 184 }
 185
 186 // ============ auxiliary funciontions ===================== //
 187
 188 void AbstractGrid::createGrid()
 189 {
 190     for (uint i = 0; i < m_width*m_height; ++i) {
 191         m_cells[i]->makeEmpty();
 192     }
 193
 194     // add a random server
 195     server_index = rand() % (m_width*m_height);
 196     m_cells[server_index]->setServer(true);
 197
 198     // number of cells that aren't free
 199     uint cellCount = 0;
 200     // TODO:use a global constant instead of 10 / 8
 201     const uint MinimumNumCells = m_width*m_height * 8 / 10;
 202     // retries until the minimum number of cells is big enough
 203     while (cellCount < MinimumNumCells) {
 204         QList<uint> list;
 205         list.append(server_index);
 206         if (rand() % 2) addRandomCable(list);
 207
 208         // add some random cables...
 209         // the list empties if there aren't many free cells left
 210         // (because of addRandomCable() not doing anything)
 211         while (!list.isEmpty()) {
 212             if (rand() % 2) {
 213                 addRandomCable(list);
 214                 if (rand() % 2) addRandomCable(list);
 215                 list.erase(list.begin());
 216             }
 217             else {
 218                 list.append(list.first());
 219                 list.erase(list.begin());
 220             }
 221         }
 222
 223         // count not empty cells
 224         cellCount = 0;
 225         for (uint i = 0; i < m_width*m_height; ++i) {
 226             if (m_cells[i]->cables() != None) ++cellCount;
 227         }
 228     }
 229 }
 230
 231 // adds a random direction and moves on (if possible)
 232 void AbstractGrid::addRandomCable(QList<uint>& list)
 233 {
 234     int cell = list.first();
 235     // find all the cells surrounding list.first()
 236     // (0 when cells don't exist)
 237     int ucell = uCell(cell); // up
 238     int rcell = rCell(cell); // right
 239     int dcell = dCell(cell); // down
 240     int lcell = lCell(cell); // left
 241
 242     QMap<Directions, int> freeCells;
 243
 244     // of those cells map the ones that are free
 245     if (ucell != NO_CELL && m_cells[ucell]->cables() == None) {
 246         freeCells[Up] = ucell;
 247     }
 248     if (rcell != NO_CELL && m_cells[rcell]->cables() == None) {
 249         freeCells[Right] = rcell;
 250     }
 251     if (dcell != NO_CELL && m_cells[dcell]->cables() == None) {
 252         freeCells[Down] = dcell;
 253     }
 254     if (lcell != NO_CELL && m_cells[lcell]->cables() == None) {
 255         freeCells[Left] = lcell;
 256     }
 257
 258     if (freeCells.isEmpty()) return; // no free cells left
 259
 260     QMap<Directions, int>::ConstIterator it = freeCells.constBegin();
 261     // move the iterator to a random direction connecting to a free cell
 262     for (int i = rand() % freeCells.count(); i > 0; --i) ++it;
 263
 264     // add the cable in the direction of cell
 265     Directions newCables = Directions(m_cells[cell]->cables() | it.key());
 266     m_cells[cell]->setCables(newCables);
 267     // add a cable in the opposite direction, on the free cell
 268     m_cells[it.value()]->setCables(invertDirection(it.key()));
 269     // append the cell that was free to the list
 270     list.append(it.value());
 271 }
 272
 273 int AbstractGrid::uCell(uint cell) const
 274 {
 275     if (cell >= m_width) {
 276         return cell - m_width;
 277     } else if (m_isWrapped) {
 278         return m_width * (m_height - 1) + cell;
 279     } else {
 280         return NO_CELL;
 281     }
 282 }
 283
 284 int AbstractGrid::dCell(uint cell) const
 285 {
 286     if (cell < m_width * (m_height - 1)) {
 287         return cell + m_width;
 288     } else if (m_isWrapped) {
 289         return cell - m_width * (m_height - 1);
 290     } else {
 291         return NO_CELL;
 292     }
 293 }
 294
 295 int AbstractGrid::lCell(uint cell) const
 296 {
 297     if (cell % m_width > 0) {
 298         return cell - 1;
 299     } else if (m_isWrapped) {
 300         return cell - 1 + m_width;
 301     } else {
 302         return NO_CELL;
 303     }
 304 }
 305
 306 int AbstractGrid::rCell(uint cell) const
 307 {
 308     if (cell % m_width < m_width - 1) {
 309         return cell + 1;
 310     } else if (m_isWrapped) {
 311         return cell + 1 - m_width;
 312     } else {
 313         return NO_CELL;
 314     }
 315 }
 316
 317 // TODO: something better to invert directions (remove duplication etc...)
 318 Directions AbstractGrid::invertDirection(Directions givenDirection)
 319 {
 320     QMap<Directions, Directions> invDirs;
 321     invDirs[Up]    = Down;
 322     invDirs[Right] = Left;
 323     invDirs[Down]  = Up;
 324     invDirs[Left]  = Right;
 325
 326     return invDirs[givenDirection];
 327 }
 328
 329
 330 int AbstractGrid::solutionCount()
 331 {
 332     MoveList possibleNextMoves;
 333     // TODO: put following in external function
 334     foreach (AbstractCell *cell, m_cells) {
 335         if (!cell->hasBeenMoved()) {
 336             Directions dirs = cell->cables();
 337             Move move;
 338             if (dirs == None) {
 339                 // no cables
 340                 move = Move(cell->index(), Move::None);
 341                 possibleNextMoves.append(move);
 342             } else if (dirs == (Up | Down) || dirs == (Left | Right)) {
 343                 // cables forming a line
 344                 move = Move(cell->index(), Move::None);
 345                 possibleNextMoves.append(move);
 346
 347                 move = Move(cell->index(), Move::Left);
 348                 possibleNextMoves.append(move);
 349             } else {
 350                 // other kind of cables
 351                 move = Move(cell->index(), Move::None);
 352                 possibleNextMoves.append(move);
 353
 354                 move = Move(cell->index(), Move::Left);
 355                 possibleNextMoves.append(move);
 356
 357                 move = Move(cell->index(), Move::Right);
 358                 possibleNextMoves.append(move);
 359
 360                 move = Move(cell->index(), Move::Inverted);
 361                 possibleNextMoves.append(move);
 362             }
 363             break;
 364         }
 365     }
 366
 367     // all cells have been moved
 368     if (possibleNextMoves.isEmpty()) {
 369         return isSolution() ? 1 : 0;
 370     }
 371     // else
 372
 373     int solutionsFound = 0;
 374     foreach (Move nextMove, possibleNextMoves) {
 375         int index = nextMove.index();
 376
 377         switch (nextMove.move()) {
 378         case Move::None:
 379             m_cells[index]->emptyMove();
 380             break;
 381         case Move::Right:
 382             m_cells[index]->turnClockwise();
 383             break;
 384         case Move::Left:
 385             m_cells[index]->turnCounterclockwise();
 386             break;
 387         case Move::Inverted:
 388             m_cells[index]->invert();
 389             break;
 390         }
 391
 392         if (movesDoneArePossible()) {
 393             solutionsFound += solutionCount(); // recursive call
 394         }
 395
 396         m_cells[index]->reset(); // undo move
 397     }
 398     return solutionsFound;
 399 }
 400
 401 bool AbstractGrid::movesDoneArePossible()
 402 {
 403
 404     foreach (AbstractCell *cell, m_cells) {
 405         if (!cell->hasBeenMoved()) continue;
 406
 407         uint x = cell->index() % m_width;
 408         uint y = cell->index() / m_width;
 409         Directions cables = cell->cables();
 410
 411         // check if there are moved cells near the borders that are wrong
 412         if (!m_isWrapped) {
 413             if (x == 0          && cables & Left)  return false;
 414             if (x == m_width-1  && cables & Right) return false;
 415             if (y == 0          && cables & Up)    return false;
 416             if (y == m_height-1 && cables & Down)  return false;
 417         }
 418
 419         // check if there are contiguous moved cells that are wrong
 420
 421         if (cables & Left) {
 422             int lcell = lCell(cell->index());
 423             if (lcell != NO_CELL && m_cells[lcell]->hasBeenMoved()) {
 424                 // also the cell to the left of the current has been moved
 425
 426                 // if it doesn't connect return false
 427                 if (!(m_cells[lcell]->cables() & Right)) return false;
 428             }
 429         }
 430         if (cables & Right) {
 431             int rcell = rCell(cell->index());
 432             if (rcell != NO_CELL && m_cells[rcell]->hasBeenMoved()) {
 433                 if (!(m_cells[rcell]->cables() & Left)) return false;
 434             }
 435         }
 436         if (cables & Up) {
 437             int ucell = uCell(cell->index());
 438             if (ucell != NO_CELL && m_cells[ucell]->hasBeenMoved()) {
 439                 if (!(m_cells[ucell]->cables() & Down)) return false;
 440             }
 441         }
 442         if (cables & Down) {
 443             int dcell = dCell(cell->index());
 444             if (dcell != NO_CELL && m_cells[dcell]->hasBeenMoved()) {
 445                 if (!(m_cells[dcell]->cables() & Up)) return false;
 446             }
 447         }
 448     }
 449
 450     // nothing was wrong
 451     return true;
 452 }
 453
 454 bool AbstractGrid::hasUnneededCables()
 455 {
 456     foreach (AbstractCell *cell, m_cells) {
 457         if (cell->isTerminal() || cell->isServer() || cell->cables() == None) {
 458             continue;
 459         }
 460
 461         Directions oldCables = cell->cables();
 462         cell->setCables(None);
 463
 464         bool solution = isSolution();
 465         cell->setCables(oldCables);
 466
 467         if (solution) {
 468             // it has a solution also when the cables of cell are removed
 469             return true;
 470         }
 471     }
 472
 473     return false;
 474 }
 475
 476 bool AbstractGrid::isSolution()
 477 {
 478     foreach (AbstractCell *cell, m_cells) {
 479         cell->setConnected(false);
 480     }
 481     updateConnections();
 482     // return false if there is a terminal that isn't connected
 483     foreach (AbstractCell *cell, m_cells) {
 484         if (cell->isTerminal() && !cell->isConnected()) {
 485             return false;
 486         }
 487     }
 488     // all terminals are connected
 489     return true;
 490 }
 491
 492 void AbstractGrid::updateConnections()
 493 {
 494     // TODO: add int AbstractGrid::cellsCount()
 495     QVector<bool> newConnections(m_width * m_height);
 496     for (uint i = 0; i < m_width * m_height; ++i) {
 497         newConnections[i] = false;
 498     }
 499
 500     // indexes of the changed cells
 501     QList<int> changedCells;
 502     changedCells.append(server_index);
 503     m_cells[server_index]->setConnected(true);
 504
 505     while (!changedCells.isEmpty())
 506     {
 507         int cell_index = changedCells.first();
 508         int uindex = uCell(cell_index);
 509         int rindex = rCell(cell_index);
 510         int dindex = dCell(cell_index);
 511         int lindex = lCell(cell_index);
 512
 513         AbstractCell *cell = m_cells[cell_index];
 514         AbstractCell *ucell = (uindex != NO_CELL) ? m_cells[uindex] : 0;
 515         AbstractCell *rcell = (rindex != NO_CELL) ? m_cells[rindex] : 0;
 516         AbstractCell *dcell = (dindex != NO_CELL) ? m_cells[dindex] : 0;
 517         AbstractCell *lcell = (lindex != NO_CELL) ? m_cells[lindex] : 0;
 518
 519         if ((cell->cables() & Up) && ucell != 0 &&
 520                 (ucell->cables() & Down) && !newConnections[uindex]) {
 521             newConnections[uindex] = true;
 522             changedCells.append(ucell->index());
 523         }
 524         if ((cell->cables() & Right) && rcell != 0 &&
 525                 (rcell->cables() & Left) && !newConnections[rindex]) {
 526             newConnections[rindex] = true;
 527             changedCells.append(rcell->index());
 528         }
 529         if ((cell->cables() & Down) && dcell != 0 &&
 530                 (dcell->cables() & Up) && !newConnections[dindex]) {
 531             newConnections[dindex] = true;
 532             changedCells.append(dcell->index());
 533         }
 534         if ((cell->cables() & Left) && lcell != 0 &&
 535                 (lcell->cables() & Right) && !newConnections[lindex]) {
 536             newConnections[lindex] = true;
 537             changedCells.append(lcell->index());
 538         }
 539         changedCells.erase(changedCells.begin());
 540     }
 541
 542     for (uint i = 0; i < m_width * m_height; i++){
 543         m_cells[i]->setConnected(newConnections[i]);
 544     }
 545 }
 546