Путешествие коня. Почему конь не хочет пробежать все возможные варианты? - C++ - Ответ 2867066

#include <iostream>
#include <iomanip>
 
std::size_t digitsInNumber( int number ) {
    int digits = 1;
 
    while ( number /= 10 )
        digits++;
 
    return digits;
}
 
void arrayOutput( const int* const *const array, const int size ) {
    std::size_t w = digitsInNumber( size * size );
 
    for ( int i = 0; i < size; i++ ) {
        for ( int j = 0; j < size; j++ )
            std::cout << std::setw( w ) << array[ i ][ j ] << ' ';
 
        std::cout << std::endl;
    }
}
 
void resetBoard( int **b, const int size ) {
    for ( int i = 0; i < size; i++ )
        for ( int j = 0; j < size; j++ )
            b[ i ][ j ] = 0;
}
 
void resetAccessibility( int **a, const int boardSize, const int vertical[], const int horizontal[], const int movesSize ) {
    resetBoard( a, boardSize );
 
    for ( int i = 0; i < boardSize; i++ ) {
        for ( int j = 0; j < boardSize; j++ )
            for ( int k = 0; k < movesSize; k++ )
                if ( i + vertical[ k ] >= 0 && i + vertical[ k ] < boardSize && j + horizontal[ k ] >= 0 && j + horizontal[ k ] < boardSize )
                    a[ i + vertical[ k ]][ j + horizontal[ k ]]++;
    }
}
 
int **initMatrix( const int size ) {
    int** tmpArr = new int*[ size ];
 
    for ( int i = 0; i < size; i++ ) {
        tmpArr[ i ] = new int[ size ];
 
        for ( int j = 0; j < size; j++ )
            tmpArr[ i ][ j ] = 0;
    }
 
    return tmpArr;
}
 
bool moveIsPosible( const int posX, const int posY, int **board, const int size ) {
    return ( posX >= 0 && posX < size && posY >= 0 && posY < size && board[ posX ][ posY ] == 0 );
}
 
int main() {
    const int sizeOfBoard = 8,
              sizeOfMoves = 8;
 
    const int vertical[ sizeOfMoves ] = { -1, -2, -2, -1, 1, 2, 2, 1 },
              horizontal[ sizeOfMoves ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
 
    int **board = initMatrix( sizeOfBoard ),
        **accessibility = initMatrix( sizeOfBoard );
 
    int currentRow = 0,
        currentColumn = 0,
        moveNumber = 0,
        move = 0,
        completeJourneys = 0;
 
    for ( int row = 0; row < sizeOfBoard; row++ ) {
        for ( int col = 0; col < sizeOfBoard; col++ ) {
            resetBoard( board, sizeOfBoard );
            resetAccessibility( accessibility, sizeOfBoard, vertical, horizontal, sizeOfMoves );
 
            currentRow = row;
            currentColumn = col;
            board[ currentRow ][ currentColumn ] = move = 1;
 
            do {
                for ( int k = 0; k < sizeOfMoves; k++ ) {
                    if ( currentRow + vertical[ k ] >= 0 && currentRow + vertical[ k ] < sizeOfBoard && currentColumn + horizontal[ k ] >= 0 && currentColumn + horizontal[ k ] < sizeOfBoard )
                        accessibility[ currentRow + vertical[ k ]][ currentColumn + horizontal[ k ]]--;
                }
 
                moveNumber = -1;
 
                for ( int k = 0; k < sizeOfMoves; k++ ) {
                    if ( moveIsPosible( currentRow + vertical[ k ], currentColumn + horizontal[ k ], board, sizeOfBoard )) {
                        if ( moveNumber == -1 )
                            moveNumber = k;
                        else if ( accessibility[ currentRow + vertical[ k ]][ currentColumn + horizontal[ k ]] < accessibility[ currentRow + vertical[ moveNumber ]][ currentColumn + horizontal[ moveNumber ]])
                            moveNumber = k;
                        else if ( accessibility[ currentRow + vertical[ k ]][ currentColumn + horizontal[ k ]] == accessibility[ currentRow + vertical[ moveNumber ]][ currentColumn + horizontal[ moveNumber ]]) {
                            int tmpMoveNumber1 = -1,
                                tmpRowPos1 = currentRow + vertical[ moveNumber ],
                                tmpColPos1 = currentColumn + horizontal[ moveNumber ],
                                tmpMoveNumber2 = -1,
                                tmpRowPos2 = currentRow + vertical[ k ],
                                tmpColPos2 = currentColumn + horizontal[ k ];
 
                            for ( int n = 0; n < sizeOfMoves; n++ ) {
                                if ( moveIsPosible( tmpRowPos1 + vertical[ n ], tmpColPos1 + horizontal[ n ], board, sizeOfBoard )) {
                                    if ( tmpMoveNumber1 == -1 )
                                        tmpMoveNumber1 = n;
                                    else if ( accessibility[ tmpRowPos1 + vertical[ n ]][ tmpColPos1 + horizontal[ n ]] < accessibility[ tmpRowPos1 + vertical[ tmpMoveNumber1 ]][ tmpColPos1 + horizontal[ tmpMoveNumber1 ]])
                                        tmpMoveNumber1 = n;
                                }
 
                                if ( moveIsPosible( tmpRowPos2 + vertical[ n ], tmpColPos2 + horizontal[ n ], board, sizeOfBoard )) {
                                    if ( tmpMoveNumber2 == -1 )
                                        tmpMoveNumber2 = n;
                                    else if ( accessibility[ tmpRowPos2 + vertical[ n ]][ tmpColPos2 + horizontal[ n ]] < accessibility[ tmpRowPos2 + vertical[ tmpMoveNumber2 ]][ tmpColPos2 + horizontal[ tmpMoveNumber2 ]])
                                        tmpMoveNumber2 = n;
                                }
                            }
 
                            if (( tmpMoveNumber1 == -1 && tmpMoveNumber2 != -1 )
                                || (( tmpMoveNumber1 != -1 && tmpMoveNumber2 != -1 )
                                     && ( accessibility[ tmpRowPos2 + vertical[ tmpMoveNumber2 ]][ tmpColPos2 + horizontal[ tmpMoveNumber2 ]] < accessibility[ tmpRowPos1 + vertical[ tmpMoveNumber1 ]][ tmpColPos1 + horizontal[ tmpMoveNumber1 ]])))
                                moveNumber = k;
                        }
                    }
                }
 
                if ( moveNumber != -1 ) {
                    currentRow += vertical[ moveNumber ];
                    currentColumn += horizontal[ moveNumber ];
                    board[ currentRow ][ currentColumn ] = ++move;
                }
 
            } while ( moveNumber != -1 );
 
            if ( move == sizeOfBoard * sizeOfBoard )
                completeJourneys++;
        }
    }
 
    for ( int i = 0; i < sizeOfBoard; i++ ) {
        delete [] board[ i ];
        delete [] accessibility[ i ];
    }
 
    delete [] board;
    delete [] accessibility;
 
    std::cout << "Size of board: " << sizeOfBoard << " * " << sizeOfBoard << "\nComplete journeys: " << completeJourneys << " of " << sizeOfBoard * sizeOfBoard << std::endl;
 
    return 0;
}