diff --git a/src/generator/sudokuboard.h b/src/generator/sudokuboard.h --- a/src/generator/sudokuboard.h +++ b/src/generator/sudokuboard.h @@ -39,6 +39,8 @@ class SKGraph; class State; +class BoardContentsPrettyPrinter; + // TODO - SudokuBoard, MathdokuGenerator, CageGenerator and DLXSolver could be // factored better. At the moment, MathdokuGenerator needs SudokuBoard's @@ -118,6 +120,7 @@ */ class SudokuBoard : public QObject { + friend class BoardContentsPrettyPrinter; Q_OBJECT public: /** @@ -272,6 +275,7 @@ void randomSequence (QVector & sequence); private: + bool generateSudokuRoxdokuTypes (BoardContents & puzzle, BoardContents & solution, Difficulty difficulty, @@ -416,19 +420,12 @@ int getSymmetricIndices (int size, Symmetry type, int cell, int * out); - /** - * Format some board-contents into text for printing, debugging output or - * saving to a file that can be loaded. - * - * @param boardValues The contents of the board to be formatted. - */ - void print (const BoardContents & boardValues); - // Methods for packing two small integers into one and unpacking them. Used // for speed and efficiency in the solver and other places. inline Pair setPair (int p, int v ) { return (p << 8) + v; } inline int pairPos (const Pair x) { return (x >> 8); } inline int pairVal (const Pair x) { return (x & 255); } }; + #endif // SUDOKUBOARD_H diff --git a/src/generator/sudokuboard.cpp b/src/generator/sudokuboard.cpp --- a/src/generator/sudokuboard.cpp +++ b/src/generator/sudokuboard.cpp @@ -34,6 +34,93 @@ #include #include +/** + * A facade to reshape the call syntax for pretty printing an instance of \c BoardContents on a given \c SudokuBoard. + * + * In order to work with structured logging (qCDebug()) \c operator<< should be used to push messages. + * Unfortunately for complex formatting this requires a custom \c operator<< overload. + * Also, unfortunately, there are two parameters required instead of just one so an \c operator<< overload cannot be used directly. + * Hence the following scheme: + * + * 1. A class \c BoardContentsPrettyPrinter which aggregates the required parameters (\c BoardContents and \c SudokuBoard). + * It uses a \c SudokuBoard pointer, because \c SudokuBoard is not a copyable type. + * 2 This class is explicitly marked \c friend by \c SudokuBoard in order to expose private members of \c SudokuBoard to it. + * 3. An \c operator<< overload to receive the \c QDebug stream and forward it to + * 4. A \c print method on the \c BoardContentsPrettyPrinter which contains the actual pretty printing logic. + */ +class BoardContentsPrettyPrinter { +public: + BoardContentsPrettyPrinter(const SudokuBoard* board, const BoardContents & boardValues): m_board(board), m_boardValues(boardValues) {}; +private: + const SudokuBoard * m_board; + const BoardContents m_boardValues; + + // needed because a lot of data is private to SudokuBoard, meaning the operator<< overload will not be granted direct accesss to it + // also why BoardContentsPrettyPrinter must be a friend class of SudokuBoard + QDebug print(QDebug stream) const; + + // using a separate friend function for operator<< to make sure QDebug is the left hand side operand. + friend QDebug operator<<(QDebug stream, const BoardContentsPrettyPrinter& printer); +}; + +inline QDebug operator<<(QDebug stream, const BoardContentsPrettyPrinter& printer) +{ + return printer.print(stream); +} + +QDebug BoardContentsPrettyPrinter::print(QDebug stream) const +{ + + // Used for test and debug, but the format is also parsable and loadable. + + const bool autoInsertSpace = stream.autoInsertSpaces(); + stream.nospace(); + + char nLabels[] = "123456789"; + char aLabels[] = "abcdefghijklmnopqrstuvwxy"; + int index, value; + + if (m_boardValues.size() != m_board->m_boardArea) { + stream << "Error: " << m_boardValues.size() <<" board values to be printed, " << m_board->m_boardArea << " values required."; + stream.setAutoInsertSpaces(autoInsertSpace); + return stream; + } + + int depth = m_board->m_graph->sizeZ(); // If 2-D, depth == 1, else depth > 1. + for (int k = 0; k < depth; k++) { + int z = (depth > 1) ? (depth - k - 1) : k; + for (int j = 0; j < m_board->m_graph->sizeY(); j++) { + if ((j != 0) && (j % m_board->m_blockSize == 0)) { + stream << "\n"; // Gap between square blocks. + } + int y = (depth > 1) ? (m_board->m_graph->sizeY() - j - 1) : j; + for (int x = 0; x < m_board->m_graph->sizeX(); x++) { + index = m_board->m_graph->cellIndex (x, y, z); + value = m_boardValues.at (index); + if (x % m_board->m_blockSize == 0) { + stream << " "; // Gap between square blocks. + } + if (value == m_board->m_unusable) { + stream << " '"; // Unused cell (e.g. in Samurai). + } + else if (value == 0) { + stream << " -"; // Empty cell (to be solved). + } + else { + value--; + char label = (m_board->m_order > 9) ? aLabels[value] : nLabels[value]; + stream << " " << label; // Given cell (or clue). + } + } + stream << "\n"; // End of row. + } + stream << "\n"; // Next Z or end of 2D puzzle/solution. + } + + stream.setAutoInsertSpaces(autoInsertSpace); + return stream; +} + SudokuBoard::SudokuBoard (SKGraph * graph) : m_type (graph->specificType()), @@ -277,9 +364,9 @@ setSeed(); for (int n = 0; n < nSamples; n++) { - dbo1 "SOLVE PUZZLE %d\n", n); + qCDebug(KSudokuLog, "SOLVE PUZZLE %d", n); solution = solveBoard (puzzle, nSamples == 1 ? NotRandom : Random); - dbo1 "PUZZLE SOLVED %d\n", n); + qCDebug(KSudokuLog, "PUZZLE SOLVED %d", n); analyseMoves (m_stats); fracClues = float (m_stats.nClues) / float (m_stats.nCells); m_accum.nSingles += m_stats.nSingles; @@ -289,8 +376,8 @@ m_accum.rating += m_stats.rating; avDeduced = float(m_stats.nSingles + m_stats.nSpots) / m_stats.nDeduces; - dbo2 " Type %2d %2d: clues %3d %3d %2.1f%% %3d moves %3dP %3dS %3dG " - "%3dM %3dD %3.1fR\n", + qCDebug(KSudokuLog, " Type %2d %2d: clues %3d %3d %2.1f%% %3d moves %3dP %3dS %3dG " + "%3dM %3dD %3.1fR", m_stats.type, m_stats.order, m_stats.nClues, m_stats.nCells, fracClues * 100.0, (m_stats.nCells - m_stats.nClues), @@ -304,8 +391,8 @@ avDeduced = float (m_accum.nSingles + m_accum.nSpots) / m_accum.nDeduces; m_accum.rating = m_accum.rating / nSamples; m_accum.difficulty = calculateDifficulty (m_accum.rating); - dbo1 " Av guesses %2.1f Av deduces %2.1f" - " Av per deduce %3.1f rating %2.1f difficulty %d\n", + qCDebug(KSudokuLog, " Av guesses %2.1f Av deduces %2.1f" + " Av per deduce %3.1f rating %2.1f difficulty %d", avGuesses, avDeduces, avDeduced, m_accum.rating, m_accum.difficulty); return m_accum.difficulty; @@ -316,20 +403,20 @@ { BoardContents answer = solveBoard (puzzle); if (answer.isEmpty()) { - dbo1 "checkPuzzle: There is NO SOLUTION.\n"); + qCDebug(KSudokuLog) << "checkPuzzle: There is NO SOLUTION."; return -1; // There is no solution. } if ((! solution.isEmpty()) && (answer != solution)) { - dbo1 "checkPuzzle: The SOLUTION DIFFERS from the one supplied.\n"); + qCDebug(KSudokuLog) << "checkPuzzle: The SOLUTION DIFFERS from the one supplied."; return -2; // The solution differs from the one supplied. } analyseMoves (m_stats); answer.clear(); answer = tryGuesses (Random); if (! answer.isEmpty()) { - dbo1 "checkPuzzle: There is MORE THAN ONE SOLUTION.\n"); + qCDebug(KSudokuLog) << "checkPuzzle: There is MORE THAN ONE SOLUTION."; return -3; // There is more than one solution. } @@ -371,14 +458,14 @@ } m_stats.nClues = nClues; m_stats.nCells = nCells; - dbo1 "STATS: CLUES %d, CELLS %d, PERCENT %.1f\n", nClues, nCells, + qCDebug(KSudokuLog, "STATS: CLUES %d, CELLS %d, PERCENT %.1f", nClues, nCells, nClues * 100.0 / float (nCells)); // Attempt to deduce the solution in one hit. GuessesList g = deduceValues (m_currentValues, gMode); if (g.isEmpty()) { // The entire solution can be deduced by applying the Sudoku rules. - dbo1 "NO GUESSES NEEDED, the solution can be entirely deduced.\n"); + qCDebug(KSudokuLog) << "NO GUESSES NEEDED, the solution can be entirely deduced."; return m_currentValues; } @@ -394,7 +481,7 @@ GuessesList guesses = m_states.top()->guesses(); int n = m_states.top()->guessNumber(); if ((n >= guesses.count()) || (guesses.at (0) == -1)) { - dbo2 "POP: Out of guesses at level %d\n", m_states.count()); + qCDebug(KSudokuLog, "POP: Out of guesses at level %d", m_states.count()); delete m_states.pop(); if (m_states.count() > 0) { m_moves.clear(); @@ -409,9 +496,9 @@ m_moves.append (guesses.at(n)); m_moveTypes.append (Guess); m_currentValues [pairPos (guesses.at(n))] = pairVal (guesses.at(n)); - dbo2 "\nNEXT GUESS: level %d, guess number %d\n", + qCDebug(KSudokuLog, "\nNEXT GUESS: level %d, guess number %d", m_states.count(), n); - dbo2 " Pick %d %d row %d col %d\n", + qCDebug(KSudokuLog, " Pick %d %d row %d col %d", pairVal (guesses.at(n)), pairPos (guesses.at(n)), pairPos (guesses.at(n))/m_boardSize + 1, pairPos (guesses.at(n))%m_boardSize + 1); @@ -448,7 +535,7 @@ clear (filled); // Add cells in random order, but skip cells that can be deduced from them. - dbo1 "Start INSERTING: %d solution values\n", solution.count()); + qCDebug(KSudokuLog, "Start INSERTING: %d solution values", solution.count()); randomSequence (sequence); int index = 0; @@ -483,7 +570,7 @@ break; } } - dbo1 "At index %d, added value %d, cell %d, row %d, col %d\n", + qCDebug(KSudokuLog, "At index %d, added value %d, cell %d, row %d, col %d", index, solution.at (cell), cell, cell/m_boardSize + 1, cell%m_boardSize + 1); } @@ -512,10 +599,10 @@ // No guesses until this much of the puzzle, including clues, is filled in. float guessLimit = 0.6; int noGuesses = (int) (guessLimit * m_stats.nCells + 0.5); - dbo1 "Guess limit = %.2f, nCells = %d, nClues = %d, noGuesses = %d\n", + qCDebug(KSudokuLog, "Guess limit = %.2f, nCells = %d, nClues = %d, noGuesses = %d", guessLimit, m_stats.nCells, m_stats.nClues, noGuesses); - dbo1 "Start REMOVING:\n"); + qCDebug(KSudokuLog) << "Start REMOVING:"; randomSequence (sequence); clear (vacant); @@ -527,35 +614,35 @@ } // Try removing this clue and its symmetry partners (if any). changeClues (puzzle, cell, symmetry, vacant); - dbo1 "ITERATION %d: Removed %d from cell %d\n", n, value, cell); + qCDebug(KSudokuLog, "ITERATION %d: Removed %d from cell %d", n, value, cell); // Check the solution is still OK and calculate the difficulty roughly. int result = checkPuzzle (puzzle, solution); // Do not force the human solver to start guessing too soon. if ((result >= 0) && (required != Unlimited) && (m_stats.firstGuessAt <= (noGuesses - m_stats.nClues))) { - dbo1 "removeValues: FIRST GUESS is too soon: move %d of %d.\n", + qCDebug(KSudokuLog, "removeValues: FIRST GUESS is too soon: move %d of %d.", m_stats.firstGuessAt, m_stats.nCells - m_stats.nClues); result = -4; } // If the solution is not OK, replace the removed value(s). if (result < 0) { - dbo1 "ITERATION %d: Replaced %d at cell %d, check returned %d\n", + qCDebug(KSudokuLog, "ITERATION %d: Replaced %d at cell %d, check returned %d", n, value, cell, result); changeClues (puzzle, cell, symmetry, solution); } // If the solution is OK, check the difficulty (roughly). else { m_stats.difficulty = (Difficulty) result; - dbo1 "CURRENT DIFFICULTY %d\n", m_stats.difficulty); + qCDebug(KSudokuLog, "CURRENT DIFFICULTY %d", m_stats.difficulty); if (m_stats.difficulty == required) { // Save removed positions while the difficulty is as required. tailOfRemoved.append (cell); - dbo1 "OVERSHOOT %d at sequence %d\n", + qCDebug(KSudokuLog, "OVERSHOOT %d at sequence %d", tailOfRemoved.count(), n); } @@ -580,16 +667,16 @@ if ((required != Unlimited) && (tailOfRemoved.count() > 1)) { for (int k = 0; k < tailOfRemoved.count() / 2; k++) { cell = tailOfRemoved.takeLast(); - dbo1 "Replaced clue(s) for cell %d\n", cell); + qCDebug(KSudokuLog, "Replaced clue(s) for cell %d", cell); changeClues (puzzle, cell, symmetry, solution); } } return puzzle; } void SudokuBoard::analyseMoves (Statistics & s) { - dbo1 "\nanalyseMoves()\n"); + qCDebug(KSudokuLog) << "analyseMoves()"; s.nCells = m_stats.nCells; s.nClues = m_stats.nClues; s.firstGuessAt = s.nCells - s.nClues + 1; @@ -608,29 +695,29 @@ switch (mType) { case Single: - dbo2 " Single Pick %d %d row %d col %d\n", val, pos, row+1, col+1); + qCDebug(KSudokuLog, " Single Pick %d %d row %d col %d", val, pos, row+1, col+1); m_KSudokuMoves.append (pos); s.nSingles++; break; case Spot: - dbo2 " Single Spot %d %d row %d col %d\n", val, pos, row+1, col+1); + qCDebug(KSudokuLog, " Single Spot %d %d row %d col %d", val, pos, row+1, col+1); m_KSudokuMoves.append (pos); s.nSpots++; break; case Deduce: - dbo2 "Deduce: Iteration %d\n", m); + qCDebug(KSudokuLog, "Deduce: Iteration %d", m); s.nDeduces++; break; case Guess: - dbo2 "GUESS: %d %d row %d col %d\n", val, pos, row+1, col+1); + qCDebug(KSudokuLog, "GUESS: %d %d row %d col %d", val, pos, row+1, col+1); m_KSudokuMoves.append (pos); if (s.nGuesses < 1) { s.firstGuessAt = s.nSingles + s.nSpots + 1; } s.nGuesses++; break; case Wrong: - dbo2 "WRONG GUESS: %d %d row %d col %d\n", val, pos, row+1, col+1); + qCDebug(KSudokuLog, "WRONG GUESS: %d %d row %d col %d", val, pos, row+1, col+1); break; case Result: break; @@ -645,8 +732,8 @@ // Calculate the difficulty level for empirical ranges of the rating. s.difficulty = calculateDifficulty (s.rating); - dbo1 " aM: Type %2d %2d: clues %3d %3d %2.1f%% %3dP %3dS %3dG " - "%3dM %3dD %3.1fR D=%d F=%d\n\n", + qCDebug(KSudokuLog, " aM: Type %2d %2d: clues %3d %3d %2.1f%% %3dP %3dS %3dG " + "%3dM %3dD %3.1fR D=%d F=%d", m_stats.type, m_stats.order, s.nClues, s.nCells, ((float) s.nClues / s.nCells) * 100.0, s.nSingles, s.nSpots, s.nGuesses, (s.nSingles + s.nSpots + s.nGuesses), @@ -681,52 +768,6 @@ return d; } -void SudokuBoard::print (const BoardContents & boardValues) -{ - // Used for test and debug, but the format is also parsable and loadable. - - char nLabels[] = "123456789"; - char aLabels[] = "abcdefghijklmnopqrstuvwxy"; - int index, value; - - if (boardValues.size() != m_boardArea) { - printf ("Error: %d board values to be printed, %d values required.\n\n", - boardValues.size(), m_boardArea); - return; - } - - int depth = m_graph->sizeZ(); // If 2-D, depth == 1, else depth > 1. - for (int k = 0; k < depth; k++) { - int z = (depth > 1) ? (depth - k - 1) : k; - for (int j = 0; j < m_graph->sizeY(); j++) { - if ((j != 0) && (j % m_blockSize == 0)) { - printf ("\n"); // Gap between square blocks. - } - int y = (depth > 1) ? (m_graph->sizeY() - j - 1) : j; - for (int x = 0; x < m_graph->sizeX(); x++) { - index = m_graph->cellIndex (x, y, z); - value = boardValues.at (index); - if (x % m_blockSize == 0) { - printf (" "); // Gap between square blocks. - } - if (value == m_unusable) { - printf (" '"); // Unused cell (e.g. in Samurai). - } - else if (value == 0) { - printf (" -"); // Empty cell (to be solved). - } - else { - value--; - char label = (m_order > 9) ? aLabels[value] : nLabels[value]; - printf (" %c", label); // Given cell (or clue). - } - } - printf ("\n"); // End of row. - } - printf ("\n"); // Next Z or end of 2D puzzle/solution. - } -} - GuessesList SudokuBoard::deduceValues (BoardContents & boardValues, GuessingMode gMode = Random) { @@ -736,23 +777,23 @@ iteration++; m_moves.append (iteration); m_moveTypes.append (Deduce); - dbo2 "DEDUCE: Iteration %d\n", iteration); + qCDebug(KSudokuLog, "DEDUCE: Iteration %d", iteration); bool stuck = true; int count = 0; GuessesList guesses; for (int cell = 0; cell < m_boardArea; cell++) { if (boardValues.at (cell) == m_vacant) { GuessesList newGuesses; qint32 numbers = m_validCellValues.at (cell); - dbo3 "Cell %d, valid numbers %03o\n", cell, numbers); + qCDebug(KSudokuLog, "Cell %d, valid numbers %03o", cell, numbers); if (numbers == 0) { - dbo2 "SOLUTION FAILED: RETURN at cell %d\n", cell); + qCDebug(KSudokuLog, "SOLUTION FAILED: RETURN at cell %d", cell); return solutionFailed (guesses); } int validNumber = 1; while (numbers != 0) { - dbo3 "Numbers = %03o, validNumber = %d\n", + qCDebug(KSudokuLog, "Numbers = %03o, validNumber = %d", numbers, validNumber); if (numbers & 1) { newGuesses.append (setPair (cell, validNumber)); @@ -764,7 +805,7 @@ m_moves.append (newGuesses.first()); m_moveTypes.append (Single); boardValues [cell] = pairVal (newGuesses.takeFirst()); - dbo3 " Single Pick %d %d row %d col %d\n", + qCDebug(KSudokuLog, " Single Pick %d %d row %d col %d", boardValues.at (cell), cell, cell/m_boardSize + 1, cell%m_boardSize + 1); updateValueRequirements (boardValues, cell); @@ -793,7 +834,7 @@ for (int group = 0; group < m_nGroups; group++) { QVector cellList = m_graph->clique (group); qint32 numbers = m_requiredGroupValues.at (group); - dbo3 "Group %d, valid numbers %03o\n", group, numbers); + qCDebug(KSudokuLog, "Group %d, valid numbers %03o", group, numbers); if (numbers == 0) { continue; } @@ -812,16 +853,16 @@ index++; } if (newGuesses.isEmpty()) { - dbo2 "SOLUTION FAILED: RETURN at group %d\n", group); + qCDebug(KSudokuLog, "SOLUTION FAILED: RETURN at group %d", group); return solutionFailed (guesses); } else if (newGuesses.count() == 1) { m_moves.append (newGuesses.first()); m_moveTypes.append (Spot); cell = pairPos (newGuesses.takeFirst()); boardValues [cell] = validNumber; - dbo3 " Single Spot in Group %d value %d %d " - "row %d col %d\n", + qCDebug(KSudokuLog, " Single Spot in Group %d value %d %d " + "row %d col %d", group, validNumber, cell, cell/m_boardSize + 1, cell%m_boardSize + 1); updateValueRequirements (boardValues, cell); @@ -910,7 +951,7 @@ } solveBoard (m_currentValues); - dbo1 "BOARD FILLED\n"); + qCDebug(KSudokuLog) << "BOARD FILLED"; return m_currentValues; } @@ -945,10 +986,9 @@ // example 9 bits for a 9x9 grid with 3x3 blocks. qint32 allValues = (1 << m_order) - 1; - dbo2 "Enter setUpValueRequirements()\n"); - if (dbgLevel >= 2) { - this->print (boardValues); - } + qCDebug(KSudokuLog) << "Enter setUpValueRequirements()"; + const BoardContentsPrettyPrinter prettyPrinter(this, boardValues); + qCDebug(KSudokuLog) << prettyPrinter; // Set bit-patterns to show what values each row, col or block needs. // The starting pattern is allValues, but bits are set to zero as the @@ -1001,7 +1041,7 @@ index++; } } - dbo2 "Finished setUpValueRequirements()\n"); + qCDebug(KSudokuLog) << "Finished setUpValueRequirements()"; dbo3 "allowed:\n"); for (int i = 0; i < m_boardArea; i++) {