c++ - 找不到小内存泄漏的来源

Question

我创建了一个程序，可以使用强力回溯算法解决 C++ 中的数独谜题，但是在分析 valgrind 中的内存使用情况后，我注意到它有一个小泄漏。我知道一个 GCC 错误，它导致 1 个丢失的免费字节和 72,704 个字节仍然可以访问。

我似乎缺少 903 free()/delete/delete[] 调用，它们占用了大约 100KB 的内存。

有谁知道导致内存泄漏的原因以及如何修复它？

回溯器.cpp

#include "Backtracker.h"

/**
 * Clears all dynamic memory in the list.
 * @param lst: the pointer to the list to be cleared
 */
static void clearList(std::list<Grid*> *lst) {
    std::list<Grid*>::iterator it;
    for (unsigned int i = 0; i < lst->size(); i++) {
        it = lst->begin();
        std::advance(it, i);
        delete *it;
    }
    delete lst;
}

/**
 * Solves the sudoku puzzle or returns a null if there is no solution.
 * @param g: a pointer to the starting grid
 * @return: a pointer to the solution
 */
Grid* solve(Grid *g) {
    if (g->isGoal()) {
        return g;
    }

    std::list<Grid*> *successors = g->getSuccessors();
    std::list<Grid*>::iterator it;

    for (unsigned int i = 0; i < successors->size(); i++) {
        it = successors->begin();
        std::advance(it, i);

        if ((*it)->isValid()) {
            Grid *solution = solve(*it);
            if (solution != nullptr) {
                solution = solution->copyGrid();
                clearList(successors);
                return solution;
            }
        }
    }
    clearList(successors);

    return nullptr;
}`

网格.cpp

#include "Grid.h"

/**
 * Constructor for the Grid class.
 */
Grid::Grid() {
    grid = new int*[SIZE];

    for (int i = 0; i < SIZE; i++) {
        grid[i] = new int[SIZE];
    }

    currRow = 0;
    currCol = 0;
}

/**
 * Destructor for the Grid class.
 */
Grid::~Grid() {
    for (int i = 0; i < SIZE; i++) {
        delete[] grid[i];
    }

    delete[] grid;
}

/**
 * Getter for any value in the grid.
 * @param row: the index of the row
 * @param col: the index of the column
 * @return: the value at the given row and column indexes
 */
int Grid::getValue(int row, int col) {
    return grid[row][col];
}

/**
 * Setter for any value in the grid.
 * @param row: the index of the row
 * @param col: the index of the column
 * @param value: the value to set at the given row and column
 */
void Grid::setValue(int row, int col, int value) {
    grid[row][col] = value;
}

/**
 * Allocates dynamic memory for a new grid and copies over the contents.
 * @return: a pointer to the new grid object
 */
Grid* Grid::copyGrid() {
    Grid *copy = new Grid();

    for (int r = 0; r < SIZE; r++) {
        for (int c = 0; c < SIZE; c++) {
            copy->setValue(r, c, grid[r][c]);
        }
    }

    copy->currRow = currRow;
    copy->currCol = currCol;

    return copy;
}

/**
 * Creates a list of successors by moving the cursor and setting the next value.
 * @return: a list of the successors
 */
std::list<Grid*>* Grid::getSuccessors() {
    std::list<Grid*> *successors = new std::list<Grid*>();

    if (canMove()) {
        Grid *copy = copyGrid();
        copy->moveCursor();
        if (copy->getValue(currRow, currCol) != 0) {
            successors->push_back(copy);
            return successors;
        } else {
            delete copy;
        }
        for (int i = 0; i < SIZE; i++) {
            copy = copyGrid();
            copy->moveCursor();
            copy->setValue(currRow, currCol, i + 1);
            if (copy->isValid()) {
                successors->push_back(copy);
            } else {
                delete copy;
            }
        }
    }

    return successors;
}

/**
 * Determines if the current configuration could be a possible solution.
 * @return: true if it could be a solution, false if not
 */
bool Grid::isValid() {
    // Checks each row for a duplicate number.
    for (int r = 0; r < SIZE; r++) {
        bool nums[SIZE] = {false * SIZE};
        for (int c = 0; c < SIZE; c++) {
            if ((grid[r][c] > 0) && (!nums[grid[r][c] - 1])) {
                nums[grid[r][c] - 1] = true;
            } else if ((grid[r][c] > 0) && (nums[grid[r][c] - 1])) {
                return false;
            }
        }
    }

    // Checks each column for a duplicate number.
    for (int c = 0; c < SIZE; c++) {
        bool nums[SIZE] = {false * SIZE};
        for (int r = 0; r < SIZE; r++) {
            if ((grid[r][c] > 0) && (!nums[grid[r][c] - 1])) {
                nums[grid[r][c] - 1] = true;
            } else if ((grid[r][c] > 0) && (nums[grid[r][c] - 1])) {
                return false;
            }
        }
    }

    // Checks squares.
    int val;
    for (int sRow = 0; sRow < SQUARES; sRow++) {
        for (int sCol = 0; sCol < SQUARES; sCol++) {
            bool nums[SIZE] = {false * SIZE};
            for (int r = 0; r < SQUARES; r++) {
                for (int c = 0; c < SQUARES; c++) {
                    val = grid[(sRow * 3) + r][(sCol * 3) + c];
                    if ((val > 0) && (!nums[val - 1])) {
                        nums[val - 1] = true;
                    } else if ((val > 0) && (nums[val - 1])) {
                        return false;
                    }
                }
            }
        }
    }

    return true;
}

/**
 * Determines if the current configuration is a solution or not.
 * @return: true if it is a solution, false if not
 */
bool Grid::isGoal() {
    for (int r = 0; r < SIZE; r++) {
        for (int c = 0; c < SIZE; c++) {
            if (grid[r][c] <= 0 || grid[r][c] > 9) {
                return false;
            }
        }
    }

    return isValid();
}

/**
 * Determines if the cursor can be advanced a position or not.
 * @return: true if the cursor can be moved, false if it is at the last position of the board
 */
bool Grid::canMove() {
    return !((currRow == SIZE - 1) && (currCol == SIZE));
}

/**
 * Moves the cursor to the next position if it is not at the last position of the board.
 * @return: true if the cursor was moved, false if it cannot be moved
 */
bool Grid::moveCursor() {
    if (!canMove()) {
        return false;
    } else {
        if (currCol != SIZE - 1) {
            currCol++;
            return true;
        } else {
            currCol = 0;
            if (currRow == SIZE - 1) {
                return false;
            } else {
                currRow++;
                return true;
            }
        }
    }
}

/**
 * Creates a string for the given row.
 * @param row: the index of the row to generate a string for
 * @return: a string for that row
 */
std::string Grid::rowString(int row) {
    std::string output = "";
    int c;

    for (c = 0; c < 3; c++) {
        output += std::to_string(grid[row][c]) + " ";
    }
    output += "| ";

    for (c = 3; c < 6; c++) {
        output += std::to_string(getValue(row, c)) + " ";
    }
    output += "| ";

    for (c = 6; c < SIZE; c++) {
        output += std::to_string(getValue(row, c)) + " ";
    }

    return output;
}

/**
 * Creates a string representation of the entire grid.
 * @return: a string for the entire grid.
 */
std::string Grid::toString() {
    std::string output = "";

    // TODO remove this
    output += std::to_string(currRow) + "," + std::to_string(currCol) + "\n";

    int r;

    for (r = 0; r < 3; r++) {
        output += rowString(r) + "\n";
    }
    output += "---------------------\n";

    for (r = 3; r < 6; r++) {
        output += rowString(r) + "\n";
    }
    output += "---------------------\n";

    for (r = 6; r < SIZE; r++) {
        output += rowString(r) + "\n";
    }

    return output;
}`

valgrind 输出

==3021== 
==3021== HEAP SUMMARY:
==3021==     in use at exit: 106,488 bytes in 903 blocks
==3021==   total heap usage: 3,260,824 allocs, 3,259,921 frees, 121,174,996 bytes allocated
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 19 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x401A69: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 20 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x40230F: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 21 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x40230F: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 22 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x40230F: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 23 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x40230F: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 24 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x40230F: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 25 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x40230F: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 26 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x40230F: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 27 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x40230F: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 412 (16 direct, 396 indirect) bytes in 1 blocks are definitely lost in loss record 28 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x40230F: main (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== 29,664 (1,152 direct, 28,512 indirect) bytes in 72 blocks are definitely lost in loss record 31 of 32
==3021==    at 0x4C2E0EF: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3021==    by 0x402620: Grid::copyGrid() (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x404104: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021==    by 0x4040ED: solve(Grid*) (in /home/anthony/Documents/Code/c-c++-projects/Sudoku-Solver/sudoku-solver)
==3021== 
==3021== LEAK SUMMARY:
==3021==    definitely lost: 1,312 bytes in 82 blocks
==3021==    indirectly lost: 32,472 bytes in 820 blocks
==3021==      possibly lost: 0 bytes in 0 blocks
==3021==    still reachable: 72,704 bytes in 1 blocks
==3021==         suppressed: 0 bytes in 0 blocks
==3021== Reachable blocks (those to which a pointer was found) are not shown.
==3021== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==3021== 
==3021== For counts of detected and suppressed errors, rerun with: -v
==3021== ERROR SUMMARY: 11 errors from 11 contexts (suppressed: 0 from 0)

Answer 1

不确定这是你的问题，但是...根据 valgrind，问题与 Grid::copyGrid() 中分配的内存有关，因此由以下 分配的内存新的

Grid* Grid::copyGrid() {
    Grid *copy = new Grid();
    // ...
    return copy;
}

我怀疑问题(一个问题？)在 solve() 中。

if ((*it)->isValid()) {
    Grid *solution = solve(*it);
    if (solution != nullptr) {
        solution = solution->copyGrid();
        clearList(successors);
        return solution;
    }
}

观察 solve() 返回一个 solution 是通过

获得的

solution = solution->copyGrid();

因此一个分配的(新)值，但丢失了通过

获得的 solution的原始值

Grid *solution = solve(*it);

来自solve() 所以它被分配了。

我的意思是:在哪里删除 solve() 返回的值？

我想你应该这样写

if ((*it)->isValid()) {
    Grid *solution = solve(*it);
    if (solution != nullptr) {
        Grid *retSol = solution->copyGrid();
        clearList(successors);
        delete solution;
        return retSol;
    }
}

-- 编辑 --

OP 答案:

I just tried this, however it only causes a segmentation fault. Removing the delete solution; line fixes the segmentation fault, but the memory leak is still there.

我明白了...这里的问题是(如果我没记错的话)solve() 也可以返回接收到的值

Grid* solve(Grid *g) {
    if (g->isGoal()) {
        return g;
    }

嗯……

因此，如果它不同于*it，您必须仅删除它。

我不喜欢但我求婚

if ((*it)->isValid()) {
    Grid *solution = solve(*it);
    if (solution != nullptr) {
        Grid *retSol = solution->copyGrid();
        clearList(successors);

        if ( solution != *it )
           delete solution;

        return retSol;
    }
}