def nqueen(board, positions=[], row=0):
    """Solve the n-queen puzzle recursively for a given board."""
    valids = board.valid_positions(row)
    if not valids:
        return False, None

    for valid in valids:
        # Try to find a solution with queen in this position
        new_board = board.place(valid)
        positions.append(valid)
        if row == board.dim - 1:
            return True, positions
        found, final_positions = nqueen(new_board, positions=positions, row=row + 1)
        if found:
            return True, final_positions
        # There was no solution, keep trying
        positions.pop()
    # No solution found with the given board
    return False, None