/**
 * With N-Queens solution, we could know how many valid boards for certain number of Queen,
 *     since the result never change, we could just cache them, and return the cached number.
 */

int totalNQueens(int n){
    static int results[19] = {
            0,
            1,
            0,
            0,
            2,
            10,
            4,
            40,
            92,
            352,
            724,
            2680,
            14200,
            73712,
            365596,
            2279184,
            14772512,
            95815104,
            666090624,
        };
        
    return results[n];
}