An ES6 solution to the challenge: enumerate all configurations of walls within a 4 x 4 grid that would result in a valid maze. In a valid maze, 1. any space must be reachable from any other space and 2. there must be only one path between any two spaces in the maze. This solution can handle up to a 5 x 5 grid.

maze.es6

// Having derived that any valid maze must have one and only one wall emanating
// from each of its inner vertices, we express a given arrangement of walls as
// a bit array with each vertex represented by two bits, corresponding to the
// direction its wall points. The northwest corner of the maze occupies the
// most significant bit, with the remainder of the vertices ordered left to
// right, top to bottom. The represented direction is as follows:
var NORTH = 0b00, // 0
    EAST  = 0b01, // 1
    SOUTH = 0b10, // 2
    WEST  = 0b11; // 3

// Usage: node maze.es6 width height
var width = process.argv[2],
    height = process.argv[3];

if (!width || !height) {
    throw('Expected two parameters, width and height.');
}

var start = new Date();

var solutions = enumerateSolutions(width, height);

var end = new Date();
var delta = end.getTime() - start.getTime();

console.log(`Found ${solutions.length} solutions in ${delta / 1000} seconds.`);

function enumerateSolutions(width, height) {
    // From a grid of walls size (x, y), find a grid of vertices,
    // or intersections of walls, size (x - 1, y - 1).
    let vertexWidth = width - 1,
        vertexHeight = height - 1,
        vertexCount = vertexWidth * vertexHeight;

    if (vertexCount > 16) {
        // Each vertex requires two bits; throw an exception for
        // counts that would exceed 32 bits.
        throw('Vertex count exceeds maximum of 16. Try a smaller maze.');
    } else if (vertexCount < 1) {
        throw('No room for a maze in that grid.');
    }

    // We use a typed array to avoid hitting heap memory limits.
    let solutions = new Int32Array(192),
        solutionsCount = 0;

    // Ladies and gentlemen, start your recursion!
    iterate(0, 0);

    // Return a trimmed solutions array.
    return solutions.slice(0, solutionsCount);

    function iterate(vertices, step) {
        // For each of the cardinal directions...
        for (let i = 0; i < 4; i++) {
            // shift a new wall onto the bit array...
            let newVertices = vertices << 2 | i;

            // and only proceed if it wouldn't break any of the rules.
            if (!isValid(newVertices, step)) { continue; }

            if (step === vertexCount - 1) {
                // A complete maze!

                // Make sure we have sufficient space in the solutions array.
                // If not, double its size.
                if (solutions.length <= solutionsCount + 1) {
                    let arr = new Int32Array(solutions.length * 2);
                    arr.set(solutions);
                    solutions = arr;
                }

                // Add the new solution, and increment the count.
                solutions[solutionsCount] = newVertices;
                solutionsCount++;
            } else {
                // More walls to add; recurse to the next vertex.
                iterate(newVertices, step + 1);
            }
        }
    }

    function isValid(vertices, step) {
        // Two walls cannot occupy the same space, so check whether the
        // receiving vertex contains a reciprocating wall.

        let receivingVertex,
            dir = wallAtIndex(vertices, 0);

        switch (dir) {
        case NORTH:
            receivingVertex = step - vertexWidth;

            // The wall is valid if it points at the north border of the maze.
            if (receivingVertex < 0) { return true; }

            // Check for a reciprocating (south-pointing) wall.
            if (wallAtIndex(vertices, step - receivingVertex) === SOUTH) {
                return false;
            }

            break;
        case WEST:
            // The wall is valid if it points at the west border of the maze.
            if (step % vertexWidth === 0) { return true; }

            receivingVertex = step - 1;

            // Check for a reciprocating (east-pointing) wall.
            if (wallAtIndex(vertices, step - receivingVertex) === EAST) {
                return false;
            }

            break;
        default: // EAST and SOUTH
            // We recurse from the northwest corner of the maze, so
            // any east- or south-pointing walls are always okay.
            return true;
        }

        return !isLoop(vertices, step, receivingVertex);
    }

    function isLoop(vertices, step, cur) {
        // Recursively search for a loop back to the starting vertex.

        let receivingVertex,
            dir = wallAtIndex(vertices, step - cur);

        switch (dir) {
        case NORTH:
            receivingVertex = cur - vertexWidth;

            // Not a loop if we've arrived at the north border of the maze.
            if (receivingVertex < 0) { return false; }

            break;
        case EAST:
            // Not a loop if we've arrived at the east border of the maze.
            if (cur % vertexWidth === vertexWidth - 1) { return false; }

            receivingVertex = cur + 1;
            break;
        case SOUTH:
            receivingVertex = cur + vertexWidth;

            // Not a loop if we've arrived at the south border of the maze.
            if (receivingVertex > vertexCount) { return false; }

            break;
        case WEST:
            // Not a loop if we've arrived at the west border of the maze.
            if (cur % vertexWidth === 0) { return false; }

            receivingVertex = cur - 1;
            break;
        }

        // Check if we've arrived back where we started.
        if (receivingVertex === step) { return true; }

        // If the receiving vertex has yet to be instatiated, it's not a loop.
        if (receivingVertex > step) { return false; }

        // Otherwise, recurse to the receiving vertex.
        return isLoop(vertices, step, receivingVertex);
    }

    function wallAtIndex(vertices, idx) {
        // Get the two-bit wall direction from the bit array.

        let pos = idx * 2,
            mask = 0b11 << pos;

        return (vertices & mask) >>> pos;
    }
}